Problem Statement
Implement a Queue using Stack operations only.
Support:
push()
pop()
peek()
empty()
Brute Force Intuition
Use one stack.
For dequeue:
Reverse stack
Remove front
Reverse again
Very expensive.
Moving Towards the Optimal Approach
Use:
st1 → Incoming Elements
st2 → Outgoing Elements
Whenever:
st2 becomes empty
Move everything from:
st1 → st2
This reverses order automatically.
Pattern Recognition
Queue
+
Stack
=> Two Stack Reversal
Key Observation
Input:
1 2 3 4
Stored:
st1
4
3
2
1
Transfer:
st2
1
2
3
4
Now Queue order appears.
Optimal Java Solution
class MyQueue {
Stack<Integer> st1;
Stack<Integer> st2;
public MyQueue() {
st1 = new Stack<>();
st2 = new Stack<>();
}
public void push(int x) {
st1.push(x);
}
private void transfer() {
if (st2.isEmpty()) {
while (!st1.isEmpty()) {
st2.push(st1.pop());
}
}
}
public int pop() {
transfer();
return st2.pop();
}
public int peek() {
transfer();
return st2.peek();
}
public boolean empty() {
return st1.isEmpty()
&& st2.isEmpty();
}
}
Dry Run
push(1)
push(2)
push(3)
Stacks:
st1
3
2
1
Need dequeue.
Transfer:
st2
1
2
3
Pop:
1 removed
Queue order maintained.
Complexity Analysis
| Operation | Complexity |
|---|---|
| Push | O(1) |
| Pop | Amortized O(1) |
| Peek | Amortized O(1) |
| Empty | O(1) |
Interview One-Liner
Use one stack for insertion and another for removal. Transfer only when the output stack becomes empty.
Pattern Learned
Stack Using Queue
→ Rotation
Queue Using Stack
→ Reversal
Stack Using Array
→ Top Pointer
Queue Using Array
→ Front/Rear Management