visual walkthrough
Implement Queue using Stacks
Amortised O(1) with two stacks; a common design warm-up.
The idea
A queue is first-in-first-out, a stack is last-in-first-out. Pouring one stack into another reverses the order, which turns LIFO into FIFO.
Pour only when the second stack runs dry. Each item is moved at most once, so the cost per operation averages out to O(1).
Complexity
| approach | time | space |
|---|---|---|
| Reshuffle on every push | O(n) push | O(n) |
| Two stacks, pour lazily | O(1) amortised | O(n) |