Implement Stack using Queues
An easy Queue interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Queue
- Sheets
- 2
- Core for
- 10 roles
The problem
Implement a last-in-first-out stack using only two queues. The stack should support push, top, pop, and empty operations.
Example 1
- Input
- MyStack s; s.push(1); s.push(2); s.top(); s.pop(); s.empty()
- Output
- 2, 2, false
- Why
- After pushing 1 and 2, the top is 2. Popping returns 2. The stack is not empty.
Example 2
- Input
- MyStack s; s.push(1); s.pop(); s.empty()
- Output
- 1, true
Constraints
- 1 <= x <= 9
- At most 100 calls to push, top, pop, and empty
How to think about it
Updated 2026-09-29Unlike a stack, cycling elements through a queue never flips their relative order. To place the newest arrival at the exit where a stack pop expects it, rotate all preceding elements behind it immediately upon insertion, turning a FIFO structure into a self-reversing carousel.
Approaches, worst first
Two queues with costly pop
time O(n) · space O(n)
Enqueue into q1. For each pop or top, migrate all but the final element into q2, read or remove that trailing item, and swap queue references. Rebuilding the prefix on every read is clumsy and slows down queries.
Single queue with push rotationWrite this one
time O(n) · space O(n)
Push the new element into a single queue, then immediately dequeue and re-enqueue the previous size elements one by one. The new arrival is now at the front, making pop and top pure O(1) operations while discarding the second queue entirely.
Where people lose marks · 3
- Rotating size times after enqueueing rather than size - 1, which shifts the new element away from the front again.
- Caching the front element for top in a local variable that desynchronizes after an interleaved pop.
- Attempting amortized O(1) pops without paying on push. Queues cannot reverse order lazily because FIFO preserves arrival direction under any transfer.
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 .