The problem
Build a FIFO queue using only two stacks, with amortized O(1) operations.
Stuck? Reveal hints one at a time
How to approach it
- 1push: always onto the input stack.
- 2pop/peek: if the output stack is empty, drain the input stack into it (reversing order), then operate on the output top.
- 3empty: both stacks empty.
Key insight
Each element moves at most twice (in-stack → out-stack), so any sequence of n operations does O(n) total work — amortized O(1) despite occasional O(n) pops.
The solution
Watch out for
- Draining input on EVERY pop (instead of only when output is empty) destroys the amortized bound.
- peek must trigger the same drain as pop.