Write an algorithm to print out all the valid permutations that can be created using a stack and deque given an array of n integers.

This is a question from TAOCP,Google and I found it very interesting.

Given an array of integers, we can use stacks or deques (doubly ended queues) to output the numbers in certain permutations. For e.g. given an array {1, 2, 3, 4}, we can output it as {2, 3, 1, 4} by pushing down 1, pushing down 2, popping out 2, pushing down 3, popping out 3, popping out 1, pushing down 4 and then finally popping out 4. However, there are certain permutations that are not possible using a stack. For e.g., given an array {1, 2, 3, 4, 5, 6}, we can't create a permutation of {2, 1, 4, 6, 3, 5} using any sequence of push and pop operations on a stack. Using a deque however, it is possible. Write an algorithm to print out all the valid permutations that can be created using a stack and deque given an array of n integers.