How to Implement a Queue using Stacks

A Queue follows First In First Out order but a Stack follows Last In First Out order. These are opposites. The trick is to use two stacks together in a way that reverses the order and simulates queue behavior.

Create two stacks. Call the first one the Input Stack and the second one the Output Stack. All new elements go into the Input Stack during enqueue. All elements come out of the Output Stack during dequeue.

The enqueue operation is simple. Just push the new element onto the Input Stack. No movement between stacks happens during enqueue. This is always a constant time operation.

When dequeue is called, first check if the Output Stack is empty. If it is not empty, simply pop from the Output Stack and return the value. If it is empty, transfer all elements from the Input Stack to the Output Stack one by one by popping from Input and pushing to Output.

When you pop all elements from the Input Stack and push them onto the Output Stack, the order gets reversed. The element that was pushed first into Input Stack ends up on top of Output Stack, which is exactly the First In First Out behavior a queue requires.

Peek works the same way as dequeue but without removing the element. If the Output Stack is not empty, peek at its top. If it is empty, transfer all elements from Input to Output first, then peek at the top of Output Stack.

Each element is moved from Input Stack to Output Stack at most once in its entire lifetime. So even though a single dequeue might trigger a transfer, the amortized cost per operation across many operations is constant time. This is called amortized constant time complexity.