Suppose we have an ordered sequence(input) queue containing $1,2,..,n$. ↵
↵
We also have a stack and an "output queue". We will be using this stack to try to obtain different permutations of this sequence in the "output queue".↵
↵
At any time we may either 1) push the front ofour ordered sethe input quencue onto the stack or 2) pop the top of the stack and appendpush it to our resulting permutationthe "output queue".↵
↵
↵
Which permutations of the original sequence can be obtained by such a process in the "output queue"?↵
↵
(I ask because many programming puzzles seem to be built around this question).↵
↵
So for example if the starting sequence is $1,2,3$ we can obtain all permutations except $312$. ↵
↵
But what is the answer in general?
↵
We also have a stack and an "output queue". We will be using this stack to try to obtain different permutations of this sequence in the "output queue".↵
↵
At any time we may either 1) push the front of
↵
↵
Which permutations of the original sequence can be obtained by such a process in the "output queue"?↵
↵
(I ask because many programming puzzles seem to be built around this question).↵
↵
So for example if the starting sequence is $1,2,3$ we can obtain all permutations except $312$. ↵
↵
But what is the answer in general?
