A stack may be viewed as a machine with two instructions POP and PUSH that transforms an input sequence of data items into an output sequence. Pop-stacks are a stack-like container data type but the POP operation removes all the items on the stack. The permutations that can be sorted by a system of k pop-stacks in parallel are shown to be characterizable by a finite set of forbidden patterns and, for k = 2, a recurrence relation is found for their enumeration.

Additional Metadata
Persistent URL dx.doi.org/10.1016/S0020-0190(99)00049-6
Journal Information Processing Letters
Citation
Atkinson, M.D., & Sack, J.-R. (1999). Pop-stacks in parallel. Information Processing Letters, 70(2), 63–67. doi:10.1016/S0020-0190(99)00049-6