  We construct a non-commutative, non-cocommutative, graded bialgebra
$\mathbf{\Pi}$ with a basis indexed by the permutations in all finite symmetric
groups. Unlike the formally similar Malvenuto-Poirier-Reutenauer Hopf algebra,
this bialgebra does not have finite graded dimension. After giving formulas for
the product and coproduct, we show that there is a natural morphism from
$\mathbf{\Pi}$ to the algebra of quasi-symmetric functions, under which the
image of a permutation is its associated Stanley symmetric function. As an
application, we use this morphism to derive some new enumerative identities. We
also describe analogues of $\mathbf{\Pi}$ for the other classical types. In
these cases, the relevant objects are module coalgebras rather than bialgebras,
but there are again natural morphisms to the quasi-symmetric functions, under
which the image of a signed permutation is the corresponding Stanley symmetric
function of type B, C, or D.
