Stack and Queue Mutual Simulation
Implement a queue using two stacks and a stack using two queues, explaining the amortised cost of each approach.
Stack and Queue Mutual Simulation is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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()) # 3Amortised O(1) Analysis for Queue from Stacks
Each element is transferred from inbox to outbox at most once. When popping from outbox is O(1), and transfers occur only when outbox is empty, the total work for n pushes and n pops is at most 2n stack operations — O(n) total, O(1) amortised per operation. This means individual operations can be O(n) in the worst case but the average is O(1).
# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
def __init__(self):
self.inbox = []; self.outbox = []; self.transfers = 0
def push(self, x): self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
self.transfers += 1
return self.outbox.pop()
q = TrackedQueue()
for i in range(5):
q.push(i)
for _ in range(5):
q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers) # at most nStack Using Two Queues (Lazy Pop)
Implementing a stack with two queues is less natural because queues are FIFO. The lazy-pop approach: keep one main queue and one temporary queue. On push, enqueue to the main queue (O(1)). On pop or peek, dequeue all but the last element into the temporary queue, save the last element, then swap the queues. This is O(n) per pop but O(1) per push.
from collections import deque
class MyStack:
def __init__(self):
self.main = deque()
self.temp = deque()
def push(self, x):
self.main.append(x) # O(1)
def pop(self):
# Move all but last element to temp
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main.popleft() # the 'top'
self.main, self.temp = self.temp, self.main # swap
return val
def top(self):
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main[0]
self.temp.append(self.main.popleft())
self.main, self.temp = self.temp, self.main
return val
def empty(self):
return len(self.main) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.pop()) # 2Stack Using One Queue (Rotate on Push)
An elegant one-queue implementation: on push, enqueue the new element, then rotate the queue so the new element is at the front. Rotating means dequeueing and re-enqueueing all elements that were there before the push. Pop and peek are then O(1) (just dequeue/peek front). Push is O(n) — the opposite trade-off from the two-queue version.
from collections import deque
class MyStackOneQueue:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate: move all preceding elements behind x
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2Trade-off Summary: Which Variant to Choose?
For queue from two stacks: push O(1), pop/peek O(1) amortised — prefer when pop operations are frequent. For stack from two queues: push O(1), pop O(n) — prefer when pushes are far more frequent than pops. For stack from one queue: push O(n), pop O(1) — prefer when pops dominate. State these trade-offs explicitly in an interview to demonstrate that you think beyond just 'it works'.
print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue: push O(n), pop O(1)')Why Does Reversing Restore FIFO?
When elements 1, 2, 3 are pushed onto a stack (inbox), they sit in order bottom-to-top as 1, 2, 3. Popping all into a second stack (outbox) reverses the order: outbox has 3 at bottom and 1 at top. Popping from outbox gives 1, then 2, then 3 — exactly FIFO insertion order. This is why exactly two reversals (two stacks) restore FIFO, while a single stack would give LIFO.
# Demonstrate double-reversal = FIFO
inbox = [1, 2, 3] # pushed in this order
outbox = []
while inbox:
outbox.append(inbox.pop())
print('outbox (one reversal):', outbox) # [3, 2, 1] top-to-bottom
# Pop from outbox gives FIFO
result = []
while outbox:
result.append(outbox.pop())
print('dequeued:', result) # [1, 2, 3] — FIFO!LeetCode 232: Implement Queue Using Stacks
LeetCode 232 is the direct 'queue from two stacks' problem. The expected solution is the lazy outbox transfer. In an interview: state that each element moves from inbox to outbox at most once, making all operations amortised O(1). Mention that individual pop calls can be O(n) in the worst case (when outbox is empty) but the average over n operations is O(1).
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # ensure outbox is populated
return self.outbox.pop()
def peek(self):
if not self.outbox:
while self.inbox: # transfer lazily
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.empty()) # FalseLeetCode 225: Implement Stack Using Queues
LeetCode 225 is the 'stack from queues' problem. The one-queue rotate-on-push solution is the cleanest. After pushing element x, rotate the queue by moving all elements that were already there to behind x. This costs O(n) per push but makes top and pop O(1). State the trade-off and confirm it matches the constraints (e.g., push-light or pop-heavy workload).
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x): # O(n)
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self): # O(1)
return self.q.popleft()
def top(self): # O(1)
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2
print(s.empty()) # FalseExtending to Three Stacks in One Array
A related design challenge: implement three stacks using a single array. One approach divides the array into three equal fixed sections. A more flexible approach uses interleaved storage with pointers, growing each stack from its region and copying when boundaries collide. This tests dynamic array management and is asked at senior-level interviews. The fixed-section approach is simpler but wastes space if stacks grow unevenly.
class ThreeStacks:
def __init__(self, size):
self.data = [0] * (3 * size)
self.tops = [-1, -1, -1] # relative top of each stack
self.size = size
def push(self, stack_num, val):
self.tops[stack_num] += 1
if self.tops[stack_num] >= self.size:
raise OverflowError('stack full')
self.data[stack_num * self.size + self.tops[stack_num]] = val
def pop(self, stack_num):
if self.tops[stack_num] < 0:
raise IndexError('stack empty')
val = self.data[stack_num * self.size + self.tops[stack_num]]
self.tops[stack_num] -= 1
return val
ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2)) # 10 20 30Key Takeaways: Simulation Patterns
The mutual simulation problems teach a broader principle: any data structure can be built from another given enough intermediate buffering and reversal. The cost of the simulation depends on which operations you optimise — you can always make push O(1) or pop O(1), but making both O(1) requires amortisation or multiple auxiliary structures.
In an interview, always ask: 'Which operations are more frequent?' This guides the choice of implementation variant and signals senior-level thinking about operational requirements.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: a queue from two stacks achieves O(1) amortised pop by lazily transferring elements from inbox to outbox, a stack from one queue achieves O(1) pop by rotating the queue on every push (O(n) push), and the choice of which operation to make O(1) depends on the usage pattern. Next up we explore hash map internals and collision handling.
Frequently asked questions
Is the “Stack and Queue Mutual Simulation” lesson free?
Yes — the full text of “Stack and Queue Mutual Simulation” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Stack and Queue Mutual Simulation”?
Implement a queue using two stacks and a stack using two queues, explaining the amortised cost of each approach. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Stack and Queue Mutual Simulation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Stack Implementation and Applications
- Queue Implementation and Deque
- Monotonic Stack Pattern
- Stack and Queue Mutual Simulation