Abstract
A fork stack is a stack that allows pushes and pops of several items at a time. An algorithm to determine which sequences of input streams can be sorted by a fork stack is given. The minimal unsortable sequences are found (there are a finite number only). The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time. Some enumeration results for the number of sortable sequences are given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. D. Atkinson: Restricted permutations, Discrete Math. 195 (1999), 27–38.
M. D. Atkinson: Generalised stack permutations, Combinatorics, Probability and Computing 7 (1998), 239–246.
P. Flajolet and A. M. Odlyzko: Singularity analysis of generating functions. SIAM Jour. Disc. Math. 2 (1990), 216–240.
P. Flajolet and R. Sedgwick: The Average Case Analysis of Algorithms, Complex Asymptotics and Generating Functions. INRIA Research Report 2026, 1993.
I. P. Goulden, D. M. Jackson: Combinatorial Enumeration, John Wiley and Sons, New York, 1983.
D. E. Knuth: Fundamental Algorithms, The Art of Computer Programming Vol. 1 (First Edition), Addison-Wesley, Reading, Mass. (1967).
V. R. Pratt: Computing permutations with double-ended queues, parallel stacks and parallel queues, Proc. ACM Symp. Theory of Computing 5 (1973), 268–277.
N. J. A. Sloane: The Online Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences/, 2002.
R. E. Tarjan: Sorting using networks of queues and stacks, Journal of the ACM 19 (1972), 341–346.
H. S. Wilf: generatingfunctionology, Academic Press, New York, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albert, M.H., Atkinson, M.D. (2002). Sorting with a Forklift. In: Penttonen, M., Schmidt, E.M. (eds) Algorithm Theory — SWAT 2002. SWAT 2002. Lecture Notes in Computer Science, vol 2368. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45471-3_38
Download citation
DOI: https://doi.org/10.1007/3-540-45471-3_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43866-3
Online ISBN: 978-3-540-45471-7
eBook Packages: Springer Book Archive