\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf M.H. Albert and M.D. Atkinson }
%
%
\medskip
\noindent
%
%
{\bf Sorting with a Forklift}
%
%
\vskip 5mm
\noindent
%
%
%
%
A fork stack is a generalised stack which allows pushes and pops of
several items at a time. We consider the problem of determining which
input streams can be sorted using a single forkstack, or dually, which
permutations of a fixed input stream can be produced using a single
forkstack. An algorithm is given to solve the sorting problem and the
minimal unsortable sequences are found. The results are extended to
fork stacks where there are bounds on how many items can be pushed and
popped at one time. In this context we also establish how to enumerate
the collection of sortable sequences.
\bye