Generate permutation using a single stack

Question

Can anyone please explain algorithm to generate the permutations possible when using only a single stack and push and pop are the only operations allowed. Have searched about it a lot, but no definite answer. Also the total number of such permutations is given by catalan numbers. But I fail to get a proof for that. Kindly explain that as well if possible.

Thanks!!

Answer 1

This problem uses an input queue and an output queue as well as a stack.

The operations are "push an item from the input queue onto the stack" and "pop an item from the stack onto the output queue".

                  1 2 3
output  ______   ______  input  
              \ /
        <--+   |   +---
       pop |   |   | push
           |   |   v

             stack

For example, with the input 1 2 3, you can get the output 2 1 3 with the following sequence:

• push 1 from input to stack
• push 2 from input to stack
• pop 2 from stack to output
• pop 1 from stack to output
• push 3 from input to stack
• pop 3 from stack to output

But you'll have a hard time if you try to generate 3 1 2.

---

How do you generate all the permutations that are possible with these operations? Well, it's trivial to do recursively: in any given state (where the "state" consists of the contents of the input queue, the stack, and the output queue), there are at most two possible operations you can perform (you can push if there is at least one item on the input queue; you can pop if there is at least one item on the stack), which will give you at most two possible new states to explore.

For further detail regarding this problem, and the relationship with Catalan numbers, go and find a copy of Knuth's "The Art of Computer Programming", volume 1 (3rd ed.) - it's discussed in §2.2.1; see exercises 2 - 5 on pp. 242-243 (and a better version of my diagram on p. 240!).