Stack and Queue Mutual Simulation
Implement a queue using two stacks and a stack using two queues, explaining the amortised cost of each approach.
Why Simulate One with the Other?
Implementing a queue using two stacks and a stack using two queues are classic design interview questions. They test your understanding of both data structures' invariants and your ability to maintain one structure's guarantee while using primitives from another. Interviewers also use these as a gateway to discuss amortised complexity.
The key insight: stacks are LIFO and queues are FIFO. To convert between them you must reverse order — and reversing a stack into another stack produces the original insertion order, which is FIFO.
Queue Using Two Stacks (Lazy Approach)
The lazy approach: use an inbox stack for pushes and an outbox stack for pops. When dequeue is called, if outbox is empty, transfer all elements from inbox to outbox — this reversal restores FIFO order. If outbox is not empty, pop directly from it. Transfers happen lazily, amortising the O(n) transfer cost over many operations.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.pop()) # 2
q.push(4)
print(q.pop()) # 3All lessons in this course
- Stack Implementation and Applications
- Queue Implementation and Deque
- Monotonic Stack Pattern
- Stack and Queue Mutual Simulation