Stack Using Queues
Rotate the queue after each push so the newest item sits at the front.
Stack: Built from one queue: rotate after each push
3 is behind 1 older item. Each rotation dequeues the front and enqueues it at the back, so after 1 rotations every older item has gone round once and 3 is at the front.
Cost
- Best
- O(1)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Push is O(n) pop O(1) in this variant.
Related
Taught by the same lesson
Stack covers these too, in the same run.