#225
Implement Stack using Queues
Easy Rotate on push
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Build a LIFO stack (push, pop, top, empty) using only queue operations.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: LIFO behaviour from a queue.
Why this works: after adding x, rotate the older items behind it, so x is at the front.
Example: push 1, push 2
[1] → add 2 → [1, 2] → rotate → [2, 1]pop → 2
✦Hints open one at a time
After adding a new element to the back, rotate the older elements behind it.
Then the newest element is always at the front of the queue.
↗Approach
One queue. push: offer x, then poll and re-offer the previous size elements. pop/top are just poll/peek.
</>Solution (Java)
import java.util.*;
class MyStack {
private final Queue<Integer> q = new LinkedList<>();
public void push(int x) {
q.offer(x);
for (int i = 0; i < q.size() - 1; i++) q.offer(q.poll()); // move older items behind x
}
public int pop() {
return q.poll();
}
public int top() {
return q.peek();
}
public boolean empty() {
return q.isEmpty();
}
}!Common mistake
Using a Deque's stack methods (push/pop) — that defeats the exercise. Stick to offer/poll/peek.
Complexity
- Time: push O(n), pop/top O(1).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon