Implement Queue using Stacks
An easy Queue interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Queue
- Sheets
- 3
- Core for
- 10 roles
The problem
Implement a first-in-first-out queue using only two stacks. The queue should support push, pop, peek, and empty operations.
Example 1
- Input
- MyQueue q; q.push(1); q.push(2); q.peek(); q.pop(); q.empty()
- Output
- 1, 1, false
- Why
- After pushing 1 and 2, the front is 1. Popping returns 1. The queue is not empty after popping.
Example 2
- Input
- MyQueue q; q.push(1); q.pop(); q.empty()
- Output
- 1, true
Constraints
- 1 <= x <= 9
- At most 100 calls to push, pop, peek, and empty
- All operations are valid
How to think about it
Updated 2026-09-29One stack reverses order, so pouring it into a second stack reverses it back into FIFO order. You do not need to shuttle items back and forth on every action; leave elements in the output stack until it runs completely dry, and the transfer cost amortizes cleanly across every element.
Approaches, worst first
Eager transfer on push
time O(n) · space O(n)
Move everything from the main stack to an auxiliary stack, push the new item, and dump everything back. Keeps the front element on top at all times for O(1) pops, but forces every single insertion to pay for the entire history.
Lazy transfer on popWrite this one
time O(1) · space O(n)
Push directly into an in-stack. When popping or peeking, draw from an out-stack; only when the out-stack is empty do you dump all elements from the in-stack. Each element moves between stacks at most twice across its lifetime, yielding true O(1) amortized cost.
Where people lose marks · 3
- Transferring from in-stack to out-stack while out-stack still holds elements. Doing so places newer elements above older ones and destroys the arrival sequence.
- Reporting empty as true when in-stack has items but out-stack is drained. Both stacks must be empty for the entire queue to be empty.
- Forgetting to update or refill out-stack during peek, causing peek and pop to observe different heads.
The theory behind it
Queue — the ground this problem stands on. All Queue problems
What Queue is
A queue is an orderly checkout line at a grocery store counter where patrons enter at the back and leave from the front. The person who arrives first gets served first, while newcomers wait patiently behind whoever came before them. Unlike a stack which turns back on its latest arrival, a queue preserves fair chronological arrival order, processing tasks strictly from oldest to newest.
When to reach for it
Reach for a queue when exploring states level by level, such as finding the shortest path across an unweighted graph or traversing a tree horizontally. It fits rate-limiting buffers, print spools, asynchronous task schedulers, and sliding cache windows where oldest items expire first. Any problem stating that processing must honor strict time-of-arrival order is an immediate candidate.
How the pattern works
Track two distinct ends: an enqueue boundary at the tail and a dequeue boundary at the head. In breadth traversals, snapshot the queue size before starting an inner loop to process an entire depth tier in one grouped wave. Items currently enqueued represent the frontier of known but unresolved states. Ensure newly generated states are marked visited upon insertion rather than upon extraction to prevent duplicated queue entries.
More Queue problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .