How Would You Implement a Stack Using Queues?
Learn how to implement a stack using one or two queues, with push-costly and pop-costly tradeoffs and Python code.
Expected Interview Answer
A stack (LIFO) can be built from one or two FIFO queues by rotating the queue after every push so the newest element sits at the front, which makes push O(n) and pop/top O(1), or by rotating on pop instead so push stays O(1) and pop becomes O(n).
With the push-costly approach, you enqueue the new element then rotate the queue by dequeuing and re-enqueuing every prior element behind it, so the most recently pushed item is always at the front and a plain dequeue acts as pop. The alternative keeps push as a simple enqueue and instead, on pop, dequeues n-1 elements back onto a second queue to expose the last-inserted one, then swaps queue references. Either way you are simulating LIFO order using only FIFO primitives (enqueue/dequeue), and one of push or pop must absorb an O(n) cost because a queue has no native way to reach its far end cheaply. Interviewers use this to test whether you understand the structural gap between LIFO and FIFO, not just whether you can call library methods.
- Tests true understanding of LIFO vs FIFO semantics
- Only uses queue primitives (enqueue/dequeue), no direct indexing
- Demonstrates the classic push-costly vs pop-costly tradeoff
- Foundation for other adapter-style data structure problems
AI Mentor Explanation
Imagine a single-file boundary rope where fielders can only join at one end and leave from the other, like a queue, but you need the last fielder who joined to be the first one sent onto the field, like a stack. Every time a new fielder joins the rope, you walk the whole line around so that fielder ends up at the front, pushing everyone else one spot back — an O(n) shuffle for every arrival. From then on, sending someone onto the field is just taking whoever is at the front, an O(1) action, because the rotation already guaranteed the newest arrival sits there. This mirrors the push-costly stack-from-queue trick: you pay the reordering cost on entry so that exit stays trivially cheap.
Step-by-Step Explanation
Step 1
Use two queues or one queue
A single queue suffices if you rotate on push; two queues make a pop-costly version cleaner to reason about.
Step 2
Push: enqueue then rotate
Enqueue the new element, then dequeue and re-enqueue every prior element so the new one ends up at the front.
Step 3
Pop/top: just dequeue the front
Because of the rotation invariant, the front of the queue is always the most recently pushed element.
Step 4
State the complexity tradeoff
Push is O(n), pop/top is O(1) in this design; the alternative flips which operation is O(n).
What Interviewer Expects
- Explain why a raw queue cannot give LIFO order without extra work
- Walk through the rotate-on-push (or rotate-on-pop) technique clearly
- State the resulting time complexities for push, pop, and top
- Mention the two-queue variant as an equally valid alternative
Common Mistakes
- Assuming a queue can be turned into a stack with O(1) push and O(1) pop simultaneously
- Forgetting to rotate the queue after enqueuing on push
- Mixing up which operation (push or pop) absorbs the O(n) cost
- Not handling the empty-stack case for pop and top
Best Answer (HR Friendly)
“I would use one queue and, on every push, add the new item then rotate the queue so that item ends up at the front. That way, popping is always just removing the front, which gives the last-in-first-out behavior a stack needs, even though I am only using queue operations underneath.”
Code Example
from collections import deque
class StackUsingQueue:
def __init__(self):
self.queue = deque()
def push(self, value):
self.queue.append(value)
for _ in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
def pop(self):
if not self.queue:
raise IndexError("pop from empty stack")
return self.queue.popleft()
def top(self):
return self.queue[0]
def is_empty(self):
return len(self.queue) == 0Follow-up Questions
- How would you implement it with two queues instead of one?
- How would you make pop O(1) and push O(n) instead?
- What is the space complexity of this approach?
- How would the design change if only a queue with enqueue/dequeue/size was available, no indexing?
MCQ Practice
1. In the single-queue, rotate-on-push stack implementation, what is the time complexity of push?
Each push enqueues then rotates every existing element, which is O(n) per push.
2. In that same rotate-on-push design, what is the time complexity of pop?
The rotation invariant keeps the most recently pushed element at the front, so pop is a plain O(1) dequeue.
3. Why can a plain queue not directly provide stack (LIFO) behavior?
A queue removes from the front in insertion order (FIFO); reaching the last-inserted element without extra work is not possible.
Flash Cards
How do you push in the rotate-on-push stack-from-queue design? — Enqueue the new value, then rotate the queue (dequeue and re-enqueue) n-1 times so it sits at the front.
What is the complexity tradeoff in this design? — Push is O(n), while pop and top become O(1).
What is the alternative tradeoff? — Push stays O(1); pop becomes O(n) by shifting all but the last element to a second queue.
How many queues are strictly required? — One is sufficient for the rotate-on-push version; two make the pop-costly version easier to implement.