Implement Stack using Queue
EasyRotate after each push
Problem
Implement a stack using one or two queues.
Every time you push, rotate the queue so the newest sits at the front to pop first.
The idea
A queue serves the oldest element first, so after pushing, rotate the queue by dequeuing and re-enqueuing everything ahead of the new element. The newest item then sits at the front and pop becomes O(1) — push pays the O(n) cost instead.
The trick
- One queue is enough with the rotate-on-push trick.
- Push O(n), pop and top O(1); the reverse split is also possible.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — push 1,2; pop Values: 1, 2.
1push(x): q.enqueue(x); rotate q so x is front (move others behind)2pop(): q.dequeue()Input
- array
- [1, 2]
Output
- answer
- —
Check yourself
1 quick question about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- push 1,2; pop
- Output:
- returns 2
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.