Implement Queue using Stack
Implement FIFO push/pop/peek using only stack operations.
02
Intuition
Two stacks: inbox collects pushes; outbox serves pops. Pouring inbox into outbox reverses order once — oldest lands on top. Only pour when outbox is empty, and each element makes the trip exactly once → amortized O(1).
03
Approach
1
Two one-way stacks
push → inbox. pop/peek → outbox top. Direction of each stack never changes.
2
Lazy transfer
Only when outbox runs dry, pour all of inbox into it. Elements already in outbox stay correctly ordered.
3
Amortized analysis
Each element is pushed twice and popped twice total, ever — O(1) average per operation.
04
Solution & live demo
python
▶1class MyQueue:
▶2 def __init__(self):
▶3 self.inbox, self.outbox = [], []
▶4
▶5 def push(self, x):
▶6 self.inbox.append(x)
▶7
▶8 def _shift(self):
▶9 if not self.outbox:
▶10 while self.inbox:
▶11 self.outbox.append(self.inbox.pop())
▶12
▶13 def pop(self):
▶14 self._shift()
▶15 return self.outbox.pop()
▶16
▶17 def peek(self):
▶18 self._shift()
▶19 return self.outbox[-1]
▶20
▶21 def empty(self):
▶22 return not self.inbox and not self.outbox
05
Edge cases
pop with both stacks holding items
Serve outbox; inbox must NOT be poured on top (would reorder).
peek after many mixed ops
Same rule as pop minus removal — always outbox top after a lazy pour.
06
Complexity
Time
amortized O(1)
Space
O(n)
Each element crosses stacks once.