Implement Queue using Stacks
Last Updated: March 29, 2026
Understanding the Problem
We need to build a queue (FIFO: first in, first out) using only stacks (LIFO: last in, first out). The challenge is that these two data structures have opposite ordering. When you push elements 1, 2, 3 onto a stack, popping gives you 3, 2, 1. But a queue should give you 1, 2, 3 in the same order they went in.
So the real question is: how do we reverse the order of elements using stacks? The key insight is surprisingly simple. If you push elements onto one stack and then pop them all into a second stack, the order reverses. The element that was at the bottom of the first stack ends up on top of the second stack, which is exactly the element that should come out first in a queue.
The interesting part of this problem is not whether you can solve it, but how efficiently you can do it. There are two main strategies, and they differ in which operation pays the cost of transferring elements between stacks.
Key Constraints:
1 <= x <= 9→ The values are tiny, so there are no overflow concerns. This constraint is mostly about keeping examples simple.- At most
100calls → With such a small number of operations, any approach will work performance-wise. But the follow-up asks us to think about amortized efficiency, which is the real learning goal. - All
popandpeekcalls are valid → We never need to handle the "queue is empty" edge case for these operations. This simplifies the code.
Approach 1: Push-Heavy (Eager Transfer)
Intuition
The most intuitive approach is to keep the output stack always in the correct order so that pop and peek are instant. To do this, every time we push a new element, we rearrange everything so the oldest element stays on top of the main stack.
Here is the idea: we designate one stack as our "main" stack where elements are stored in queue order (oldest on top). When a new element arrives, we move everything from the main stack to a temporary helper stack, push the new element onto the now-empty main stack, and then move everything back. The new element ends up at the bottom, and the oldest element stays on top.
Algorithm
- Maintain two stacks:
main(stores elements in queue order, oldest on top) andhelper(temporary storage during push). - push(x): Move all elements from
maintohelper. Push x ontomain. Move all elements back fromhelpertomain. - pop(): Pop from
main(the top is the oldest element). - peek(): Peek at
main(the top is the oldest element). - empty(): Check if
mainis empty.
Example Walkthrough
Code
- Time Complexity: push is O(n) where n is the number of elements in the queue. We move every element twice. pop, peek, and empty are all O(1).
- Space Complexity: O(n) for storing the elements across the two stacks.
This approach works but every push rearranges the entire queue. What if we only rearranged when someone actually needs to dequeue?
Approach 2: Pop-Heavy (Lazy Transfer) - Amortized O(1)
Intuition
Instead of doing all the work upfront during push, we can be lazy about it. The idea is to use two stacks with distinct roles: an input stack for pushing and an output stack for popping.
When we push, we just throw the element onto the input stack. No rearranging, no fuss. O(1).
When we pop or peek, we look at the output stack. If it has elements, the top is the oldest element, so we just pop from there. If the output stack is empty, we pour everything from the input stack into the output stack. This reversal puts the elements in FIFO order.
The genius of this approach is that each element is moved at most twice in its entire lifetime: once when it is pushed onto the input stack, and once when it is transferred to the output stack. So across n operations, the total work is O(n), making each operation amortized O(1).
Think about the lifecycle of a single element. It gets pushed onto the input stack once (O(1) work). At some later point, it gets popped from the input stack and pushed onto the output stack (O(1) work). Finally, it gets popped from the output stack (O(1) work). That is 3 operations total per element, regardless of how many other operations happen.
So even though a single pop call might trigger an O(n) transfer, that transfer handles all n elements at once. Those n elements will then be served by future pop calls in O(1) each, without needing another transfer. The expensive operation "pays forward" for many cheap future operations.
Algorithm
- Maintain two stacks:
input(receives pushed elements) andoutput(serves pop/peek requests). - push(x): Push x onto the input stack.
- pop(): If the output stack is empty, transfer all elements from input to output (this reverses their order). Pop from the output stack.
- peek(): If the output stack is empty, transfer all elements from input to output. Return the top of the output stack without removing it.
- empty(): Return true only if both stacks are empty.
Example Walkthrough
Code
- Time Complexity: push is O(1). pop and peek are amortized O(1). Worst case for pop/peek is O(n) when a transfer is needed, but each element is transferred at most once, so n operations cost O(n) total. empty is O(1).
- Space Complexity: O(n) where n is the total number of elements in the queue, distributed across the two stacks.