visual walkthrough
Implement Stack using Queues
The reverse exercise, to cement how both structures behave.
The idea
A stack returns the newest item first, but a queue returns the oldest. To fix that, arrange the queue so the newest item is at the front: after every push, move all older items behind it.
That makes push O(n) but pop and top O(1). A single queue is enough: rotate the older items from the front to the back.
Complexity
| approach | time | space |
|---|---|---|
| Two queues | O(n) push | O(n) |
| One queue, rotate | O(n) push | O(n) |