How Would You Implement a Queue Using Stacks?
Learn the two-stack queue pattern, why dequeue is amortized O(1), and see working Python code for this classic interview question.
Expected Interview Answer
A queue (FIFO) can be built from two stacks: an 'in' stack absorbs every enqueue in O(1), and an 'out' stack is refilled by popping everything off 'in' and pushing it onto 'out' only when 'out' is empty and a dequeue is requested, which reverses the order and exposes the oldest element on top.
Enqueue always pushes onto the 'in' stack in O(1), since stacks are cheap to push to. Dequeue checks the 'out' stack first; if it has elements, popping its top in O(1) gives the oldest remaining item because the earlier transfer reversed insertion order. If 'out' is empty, every element is popped from 'in' and pushed onto 'out', which reverses their order so the earliest-inserted item lands on top of 'out', then that top is popped and returned. Although a single transfer costs O(n), each element only ever gets moved from 'in' to 'out' once across its lifetime, so the amortized cost per dequeue is O(1). This amortized-analysis result is exactly what interviewers are probing for beyond the mechanical construction.
- Enqueue is always O(1)
- Dequeue is O(1) amortized despite occasional O(n) transfers
- Uses only stack primitives (push/pop), proving structural equivalence
- Classic setup for amortized complexity reasoning
AI Mentor Explanation
Picture two stacks of scorecards: an 'incoming' pile where each new match's card is placed on top as it finishes, and an 'archive' pile used to hand cards to a historian in chronological order. Adding a new match's card to the incoming pile is instant, just a push. When the historian asks for the oldest match and the archive pile is empty, you flip the entire incoming pile card by card onto the archive pile, which naturally reverses the order so the oldest card ends up on top. Each card only gets flipped once in its lifetime even though a flip touches the whole pile, so across many requests the average work per request stays small — this is the amortized O(1) behind a two-stack queue.
Step-by-Step Explanation
Step 1
Maintain two stacks
An 'in' stack for enqueue operations and an 'out' stack for dequeue operations.
Step 2
Enqueue: push onto in
Every enqueue is a simple O(1) push onto the 'in' stack.
Step 3
Dequeue: pop from out, refilling if empty
If 'out' is empty, pop everything from 'in' and push it onto 'out', reversing order; then pop 'out'.
Step 4
Argue amortized O(1)
Each element is transferred from in to out at most once, so total transfer work across n operations is O(n), averaging O(1) per operation.
What Interviewer Expects
- Correctly identify the two-stack (in/out) pattern
- Explain the lazy-transfer rule: only refill 'out' when it is empty
- Justify why dequeue is O(1) amortized, not worst-case O(1)
- Handle the empty-queue edge case for dequeue/peek
Common Mistakes
- Transferring elements from 'in' to 'out' on every dequeue instead of only when 'out' is empty
- Claiming dequeue is worst-case O(1) instead of amortized O(1)
- Forgetting that pushing onto out reverses order, and getting confused about which stack top to read
- Not handling the case where both stacks are empty
Best Answer (HR Friendly)
“I would keep one stack for adding new items and a second stack for removing them. New items always go on the first stack. When someone wants to remove an item and the second stack is empty, I pour everything from the first stack into the second, which flips the order so the oldest item ends up on top and can be popped, giving me first-in-first-out behavior overall.”
Code Example
class QueueUsingStacks:
def __init__(self):
self.in_stack = []
self.out_stack = []
def enqueue(self, value):
self.in_stack.append(value)
def dequeue(self):
self._transfer_if_needed()
if not self.out_stack:
raise IndexError("dequeue from empty queue")
return self.out_stack.pop()
def peek(self):
self._transfer_if_needed()
return self.out_stack[-1]
def _transfer_if_needed(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def is_empty(self):
return not self.in_stack and not self.out_stackFollow-up Questions
- What is the amortized time complexity argument for dequeue, formally?
- How would you implement it with a single stack and recursion instead?
- How does this pattern relate to how some real message queues buffer writes?
- What happens to complexity if you need to support peek frequently interleaved with enqueue?
MCQ Practice
1. In the two-stack queue design, when does the 'out' stack get refilled from 'in'?
The lazy-transfer rule only pours 'in' into 'out' when 'out' has nothing left, minimizing total transfer work.
2. What is the amortized time complexity of dequeue in the two-stack queue?
Each element is transferred between stacks at most once, so the total transfer cost over n operations is O(n), giving O(1) amortized per operation.
3. What is the time complexity of enqueue in this design?
Enqueue is always a plain push onto the 'in' stack, which is O(1).
Flash Cards
How many stacks does the standard queue-from-stacks design use? — Two: an 'in' stack for enqueue and an 'out' stack for dequeue.
When is the 'out' stack refilled? — Only lazily, when it is empty and a dequeue or peek is requested.
What is the amortized complexity of dequeue? — O(1) amortized, even though an individual transfer is O(n).
Why does the lazy-transfer rule keep total work low? — Each element moves from in to out at most once across its lifetime, bounding total transfer work to O(n) over n operations.