Queue based on single stack

Queue based on 2 stacks is generally what we usually know of and probably would be on our minds while answering such questions. We could solve the same using one stack and taking advantage of recursion. We will see how we can solve this with no additional storage.

Assume that items come out of stack in the order they must appear in the queue (FIFO). Choosing the opposite order is also possible however is not practical. To make it happen we simply need to make sure that items in the stack (LIFO) are placed in the opposite order. Items queued first must appear at the top of the stack. This basically means that in order to queue item all items must be popped, the item  pushed and then existent items pushed inversely to pop order. But we have no additional explicit storage requirement. Then store items implicitly through recursion.

Enqueue is a O(n) operation (where n is the number items in the stack). Dequeue and Peek is a O(1) operation.