#232
Implement Queue using Stacks
Easy Two stacks
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Build a FIFO queue (push, pop, peek, empty) using only stack operations.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: FIFO behaviour from LIFO stacks.
Why this works: pouring one stack into another reverses the order. Pour only when the "out" stack is empty.
Example: push 1, push 2, pop
in [1, 2] → pour → out [2, 1] (1 on top)pop → 1
✦Hints open one at a time
Use an "in" stack for pushes and an "out" stack for pops.
Only when "out" is empty, pour everything from "in" into "out" — that reverses the order.
↗Approach
push → in.push. pop/peek → if out is empty, move all of in to out, then use out's top. Each element moves at most once, so operations are amortised O(1).
</>Solution (Java)
import java.util.*;
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
public void push(int x) {
in.push(x);
}
public int pop() {
peek();
return out.pop();
}
public int peek() {
if (out.isEmpty()) {
while (!in.isEmpty()) out.push(in.pop()); // reverse once
}
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}!Common mistake
Pouring from in to out on every pop even when out isn't empty — that breaks the order.
Complexity
- Time: Amortised O(1) per operation.
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon