115. Implement Queue using Stacks
🔗 LeetCode Problem: 232. Implement Queue using Stacks
📊 Difficulty: Easy
🏷️ Topics: Stack, Queue, Design
Problem Statement
Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x)Pushes element x to the back of the queue.int pop()Removes the element from the front of the queue and returns it.int peek()Returns the element at the front of the queue.boolean empty()Returnstrueif the queue is empty,falseotherwise.
Notes: - You must use only standard operations of a stack. - You must use two stacks.
Example:
Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 1, 1, false]
🌟 Understanding the Problem
The Behavior Difference
Queue (FIFO - What we need):
Line at a coffee shop:
Person 1 joins: [1]
Person 2 joins: [1, 2]
Person 3 joins: [1, 2, 3]
front → back
Who gets served first?
→ Person 1 (who came FIRST)
This is FIFO: First In, First Out
Stack (LIFO - What we have):
Stack of books:
Add book 1: [1]
Add book 2: [2, 1]
Add book 3: [3, 2, 1]
top → bottom
Which book do you take?
→ Book 3 (the LAST one added)
This is LIFO: Last In, First Out
The Challenge: Stack gives us LAST, but Queue needs FIRST!
💡 Building Intuition - Let's Discover Together!
Question 1: What's the Core Problem?
Let's see what happens with a simple stack:
We want queue behavior:
push(1) → [1]
push(2) → [1, 2] (2 at back)
push(3) → [1, 2, 3] (3 at back)
pop() → should give us 1 (the first one added)
If we use a stack:
push(1) → [1]
push(2) → [2]
[1]
push(3) → [3]
[2]
[1]
pop() → gives us 3 (the LAST one added)
Problem: Stack gives us 3, but we want 1!
The Mismatch:
Queue: Need FIRST element (from front)
Stack: Get LAST element (from top)
They're opposites!
Question 2: How Can We Reverse the Order?
Think about physical books:
Stack of books (bottom to top): [1, 2, 3]
↑ top
We want book 1 (at bottom).
Idea: Move books to another place!
Pick up book 3, place on table → Table: [3]
Pick up book 2, place on table → Table: [3, 2]
Pick up book 1, place on table → Table: [3, 2, 1]
Now book 1 is on TOP of the table stack!
The order REVERSED!
In terms of stacks:
Stack1: [3, 2, 1] (top to bottom)
↑
top (book 3)
Transfer to Stack2:
Pop 3 from Stack1, push to Stack2 → Stack2: [3]
Pop 2 from Stack1, push to Stack2 → Stack2: [3, 2]
Pop 1 from Stack1, push to Stack2 → Stack2: [3, 2, 1]
↑
top (book 1!)
The order is REVERSED!
Now Stack2 top has 1 (the first element we added)!
The Realization:
When you transfer elements from one stack to another,
the order REVERSES!
Original order: [1, 2, 3]
After transfer: [3, 2, 1]
This is EXACTLY what we need!
Question 3: When Should We Transfer?
Option 1: Transfer on EVERY pop
push(1), push(2), push(3)
Stack1: [3, 2, 1]
Stack2: []
pop():
Transfer all to Stack2: [3, 2, 1] → [1, 2, 3]
Pop from Stack2: get 1 ✓
Transfer back to Stack1: [2, 3]
pop() again:
Transfer all to Stack2 again: [2, 3] → [3, 2]
Pop from Stack2: get 2 ✓
Transfer back...
Problem: We're transferring EVERY time!
Element 3 moved 4 times!
Very inefficient!
Option 2: Transfer ONLY when Stack2 is empty
push(1), push(2), push(3)
Stack1: [3, 2, 1]
Stack2: []
pop():
Stack2 is empty, so transfer:
Stack1: []
Stack2: [1, 2, 3]
Pop from Stack2: get 1 ✓
Stack2: [2, 3] (Don't transfer back!)
pop() again:
Stack2 is NOT empty!
No transfer needed!
Just pop from Stack2: get 2 ✓
Stack2: [3]
push(4):
Just push to Stack1
Stack1: [4]
Stack2: [3]
pop() again:
Stack2 is NOT empty!
Just pop from Stack2: get 3 ✓
Stack2: []
pop() again:
Stack2 IS empty, now transfer:
Stack1 → Stack2: [4]
Pop from Stack2: get 4 ✓
The Pattern:
Each element moved ONLY ONCE from Stack1 → Stack2!
Element 1: Stack1 → Stack2 (1 move)
Element 2: Stack1 → Stack2 (1 move)
Element 3: Stack1 → Stack2 (1 move)
Element 4: Stack1 → Stack2 (1 move)
This is OPTIMAL! Each element moves at most once!
Question 4: What Role Does Each Stack Play?
Think of it like this:
Stack1 (Input): Where new elements arrive
- All push operations go here
- Elements in "arrival order"
Stack2 (Output): Where we pop/peek from
- Transfer from Stack1 only when empty
- Elements in "reversed order" (queue order!)
- All pop/peek operations come from here
It's like a two-room system:
Room 1 (Stack1): Receiving new items
Room 2 (Stack2): Serving items (in queue order)
The Flow:
New elements → Stack1 (input room)
↓ (transfer when needed)
Stack2 (output room) → pop/peek
Transfer only when Stack2 empty!
🎨 Visual Understanding
The Transfer Magic
═══════════════════════════════════════════════════════════
After push(1), push(2), push(3):
═══════════════════════════════════════════════════════════
Stack1 (input): Stack2 (output):
[3] ← top []
[2]
[1] ← bottom
Queue view: [1, 2, 3]
front → back
═══════════════════════════════════════════════════════════
First pop() - Transfer happens:
═══════════════════════════════════════════════════════════
Transfer from Stack1 to Stack2:
Step 1: pop 3, push to Stack2
Stack1: Stack2:
[2] [3] ← top
[1]
Step 2: pop 2, push to Stack2
Stack1: Stack2:
[1] [2]
[3]
Step 3: pop 1, push to Stack2
Stack1: Stack2:
[] [1] ← top
[2]
[3]
Now pop from Stack2:
result = 1 (the FIRST element!) ✓
Stack1: Stack2:
[] [2] ← top
[3]
The order REVERSED! Stack2 has queue order!
═══════════════════════════════════════════════════════════
Next pop() - No transfer needed:
═══════════════════════════════════════════════════════════
Stack2 is NOT empty, just pop:
result = 2 ✓
Stack1: Stack2:
[] [3] ← top
═══════════════════════════════════════════════════════════
push(4) - Goes to Stack1:
═══════════════════════════════════════════════════════════
Stack1: Stack2:
[4] ← top [3] ← top
Queue view: [3, 4]
front → back
═══════════════════════════════════════════════════════════
Next pop() - Still no transfer:
═══════════════════════════════════════════════════════════
Stack2 still has elements:
result = 3 ✓
Stack1: Stack2:
[4] []
═══════════════════════════════════════════════════════════
Next pop() - Transfer again:
═══════════════════════════════════════════════════════════
Stack2 is empty, transfer from Stack1:
Stack1 → Stack2: [4]
Pop from Stack2: result = 4 ✓
🎯 The Solution Strategy
Now that we understand WHY, here's the approach:
The Two-Stack Roles
Stack1 (input): Receives all new elements
Stack2 (output): Serves all pop/peek requests
Key rule: Transfer from Stack1 to Stack2
ONLY when Stack2 is empty!
The Operations
push(x):
Just push to Stack1
(Simple! No transfer needed)
pop():
If Stack2 is empty:
Transfer all from Stack1 to Stack2
Pop from Stack2
peek():
If Stack2 is empty:
Transfer all from Stack1 to Stack2
Peek at Stack2 top
empty():
Both Stack1 and Stack2 must be empty
Why This is Optimal (Amortized O(1))
Consider adding n elements, then popping all:
Push n elements:
n × O(1) = O(n) (all go to Stack1)
First pop:
Transfer n elements: O(n)
Pop 1: O(1)
Next n-1 pops:
Just pop from Stack2: (n-1) × O(1) = O(n-1)
Total: O(n) + O(n) + O(n-1) = O(3n-1) ≈ O(n)
Total operations: 2n (n pushes, n pops)
Average: O(n) / 2n = O(1) per operation!
Key: Each element moved at most ONCE!
💻 Implementation
class MyQueue {
private Stack<Integer> stack1; // Input stack
private Stack<Integer> stack2; // Output stack
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
// Ensure stack2 has elements
if (stack2.isEmpty()) {
transferStack1ToStack2();
}
return stack2.pop();
}
public int peek() {
// Ensure stack2 has elements
if (stack2.isEmpty()) {
transferStack1ToStack2();
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
private void transferStack1ToStack2() {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
}
⏰ Time Complexity:
- push(): O(1) - Just push to stack1
- pop(): Amortized O(1) - Each element moved once
- peek(): Amortized O(1) - Same as pop
- empty(): O(1)
💾 Space: O(n) - Store n elements across two stacks
🔍 Detailed Dry Run
Operations: push(1), push(2), peek(), pop(), push(3), pop(), pop()
═══════════════════════════════════════════════════════════
Initial State
═══════════════════════════════════════════════════════════
stack1: []
stack2: []
Queue view: []
═══════════════════════════════════════════════════════════
Operation: push(1)
═══════════════════════════════════════════════════════════
Action: stack1.push(1)
State:
stack1: [1] ← top
stack2: []
Queue view: [1]
front
═══════════════════════════════════════════════════════════
Operation: push(2)
═══════════════════════════════════════════════════════════
Action: stack1.push(2)
State:
stack1: [2] ← top
[1]
stack2: []
Queue view: [1, 2]
front → back
═══════════════════════════════════════════════════════════
Operation: peek() - Want to see 1
═══════════════════════════════════════════════════════════
Check: Is stack2 empty? YES
Transfer from stack1 to stack2:
Step 1: stack2.push(stack1.pop())
Pop 2 from stack1, push to stack2
stack1: [1]
stack2: [2]
Step 2: stack2.push(stack1.pop())
Pop 1 from stack1, push to stack2
stack1: []
stack2: [2]
[1] ← top
Peek at stack2:
result = stack2.peek() = 1
State:
stack1: []
stack2: [2]
[1] ← top
Return: 1 ✓
Explanation:
Transfer REVERSED the order!
Original: [1, 2] (bottom to top in stack1)
After: [2, 1] (bottom to top in stack2)
Now stack2 top has 1 (the first element!)
═══════════════════════════════════════════════════════════
Operation: pop() - Remove 1
═══════════════════════════════════════════════════════════
Check: Is stack2 empty? NO
No transfer needed! Just pop from stack2:
result = stack2.pop() = 1
State:
stack1: []
stack2: [2] ← top
Return: 1 ✓
Queue view: [2]
front
Explanation: Stack2 still has elements in queue order!
═══════════════════════════════════════════════════════════
Operation: push(3)
═══════════════════════════════════════════════════════════
Action: stack1.push(3)
State:
stack1: [3] ← top
stack2: [2] ← top
Queue view: [2, 3]
front → back
Explanation:
New elements go to stack1 (input)
Old elements stay in stack2 (output)
═══════════════════════════════════════════════════════════
Operation: pop() - Remove 2
═══════════════════════════════════════════════════════════
Check: Is stack2 empty? NO
No transfer needed! Just pop from stack2:
result = stack2.pop() = 2
State:
stack1: [3]
stack2: []
Return: 2 ✓
Queue view: [3]
front
═══════════════════════════════════════════════════════════
Operation: pop() - Remove 3
═══════════════════════════════════════════════════════════
Check: Is stack2 empty? YES
Transfer from stack1 to stack2:
Step 1: stack2.push(stack1.pop())
Pop 3 from stack1, push to stack2
stack1: []
stack2: [3] ← top
Pop from stack2:
result = stack2.pop() = 3
State:
stack1: []
stack2: []
Return: 3 ✓
Queue is now empty!
═══════════════════════════════════════════════════════════
Summary - Element Movement Tracking
═══════════════════════════════════════════════════════════
Element 1:
push → stack1
transfer → stack2
pop from stack2
Total moves: 1 (stack1 → stack2)
Element 2:
push → stack1
transfer → stack2
pop from stack2
Total moves: 1 (stack1 → stack2)
Element 3:
push → stack1
transfer → stack2
pop from stack2
Total moves: 1 (stack1 → stack2)
Each element moved EXACTLY ONCE! ✓
This is why we get amortized O(1)!
🧪 Edge Cases
Edge Case 1: Single Element
push(1)
pop()
Result: 1 ✓
Handling:
- Stack1: [1]
- pop() triggers transfer
- Stack2: [1]
- Pop from Stack2: get 1
Works correctly!
Edge Case 2: Push After Complete Empty
push(1), pop(), push(2), pop()
Result: 1, then 2 ✓
Handling:
- First pop empties both stacks
- Second push goes to Stack1
- Second pop transfers again
No issues!
Edge Case 3: Multiple Peeks Without Pop
push(1), push(2)
peek(), peek(), peek()
Result: 1, 1, 1 ✓
Handling:
- First peek triggers transfer
- Subsequent peeks use Stack2
- No unnecessary transfers
Efficient!
Edge Case 4: Alternating Push and Pop
push(1), pop(), push(2), pop(), push(3), pop()
Result: 1, 2, 3 ✓
Handling:
- Each pop may trigger transfer
- But each element still moves once
- Amortized O(1) maintained
Still optimal!
Edge Case 5: Large Number of Pushes Then Pops
push(1...1000)
pop() × 1000
Handling:
- First 1000 pushes: O(1) each → O(1000)
- First pop: Transfer all O(1000)
- Next 999 pops: O(1) each → O(999)
Total: O(1000) + O(1000) + O(999) = O(2999)
Average per operation: O(2999) / 2000 ≈ O(1.5) ≈ O(1)
Amortized O(1) confirmed! ✓
Edge Case 6: Empty Check
empty() → true
push(1)
empty() → false
pop()
empty() → true
Handling:
- Must check BOTH stacks
- stack1.isEmpty() && stack2.isEmpty()
Correct implementation!
Edge Case 7: Peek After Push (No Transfer Yet)
push(1), push(2), push(3)
peek()
Result: 1 ✓
Handling:
- Elements in Stack1: [3, 2, 1]
- peek() triggers transfer
- Stack2: [1, 2, 3]
- Returns 1
Transfer happens on demand!
🎯 Why This Solution Works
The Three Key Insights
Insight 1: Transfer Reverses Order
Stack1 (LIFO): [1, 2, 3] (bottom to top)
↑
Added first
Transfer to Stack2:
Pop 3, 2, 1 from Stack1
Push to Stack2
Stack2 (now FIFO): [3, 2, 1] (bottom to top)
↑
First element at top!
The reversal transforms LIFO → FIFO!
Insight 2: Lazy Transfer is Optimal
Don't transfer on every operation!
Transfer only when Stack2 is empty:
- Saves unnecessary transfers
- Each element moves at most once
- Amortized O(1) time
Example:
push 100 elements → Stack1
First pop: Transfer all (O(100))
Next 99 pops: Just pop from Stack2 (99 × O(1))
Total: O(100) + O(99) = O(199)
Average: O(199) / 100 = O(1.99) ≈ O(1) per pop
Insight 3: Two Roles Make It Work
Stack1 = Input side
- Receives all pushes
- Natural LIFO order
Stack2 = Output side
- Serves all pops/peeks
- Reversed order (FIFO!)
Separation of concerns:
Input doesn't interfere with output
Transfer happens only when needed
⚠️ Common Mistakes
Mistake 1: Transferring on every pop
// ❌ WRONG - Transfer every time!
public int pop() {
transferStack1ToStack2(); // Always transfer
return stack2.pop();
}
// Elements move multiple times!
// ✓ CORRECT - Transfer only when needed
public int pop() {
if (stack2.isEmpty()) {
transferStack1ToStack2();
}
return stack2.pop();
}
Mistake 2: Transferring back to stack1
// ❌ WRONG - Undoes the reversal!
private void transfer() {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
// Then transfers back - NO!
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
// ✓ CORRECT - One-way transfer only
private void transfer() {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
// That's it! Leave elements in stack2
}
Mistake 3: Wrong empty() check
// ❌ WRONG - Only checks one stack
public boolean empty() {
return stack1.isEmpty();
// Stack2 might still have elements!
}
// ✓ CORRECT - Check both stacks
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
Mistake 4: Forgetting to check stack2 in peek()
// ❌ WRONG - Assumes stack2 has elements
public int peek() {
return stack2.peek();
// Stack2 might be empty!
}
// ✓ CORRECT - Transfer if needed
public int peek() {
if (stack2.isEmpty()) {
transferStack1ToStack2();
}
return stack2.peek();
}
🎯 Pattern Recognition
When you see:
"Implement X using Y where X and Y are opposites"
Your approach:
1. Find the transformation
(For stacks: transfer reverses order)
2. Decide when to transform
(Lazy approach is usually optimal)
3. Separate concerns
(Input vs output responsibilities)
Similar Problems: - Implement Stack using Queues (LC 225) - Min Stack (LC 155) - Max Stack (LC 716)
🧠 Interview Strategy
Step 1: Recognize the pattern
"Queue is FIFO, Stack is LIFO - they're opposites.
Need to transform LIFO to FIFO."
Step 2: The key insight
"Transferring between stacks REVERSES the order!
This is exactly what we need."
Step 3: The strategy
"Use two stacks with different roles:
- Stack1 for input (push operations)
- Stack2 for output (pop/peek operations)
Transfer from Stack1 to Stack2 only when Stack2 is empty.
This is lazy transfer - more efficient!"
Step 4: Complexity
"Each element moves at most once from Stack1 to Stack2.
Push: O(1) always
Pop/Peek: Amortized O(1)
Over many operations, average is O(1) per operation.
This is optimal!"
📝 Quick Revision Notes
🎯 Core Concept
Queue (FIFO) using two stacks (LIFO). Stack1 for push (input), Stack2 for pop/peek (output). Transfer Stack1→Stack2 only when Stack2 empty (lazy transfer). Transfer reverses order (LIFO→FIFO). Each element moves at most once = Amortized O(1).
⚡ Quick Implementation
import java.util.Stack;
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
// simply push
// Example:
// push(1) => [1]
// push(2) => [2, 1]
// push(3) => [3, 2, 1]
stack1.push(x);
}
public int pop() {
// Now we are at [3, 2, 1]
// Concept: whenever push there, simply push to stack 1 and whenever pop, do from stack 2.
// When pop from stack 2, if no element present, empty stack 1 and do complete t/f from stack 1 to stack 2.
// Now stack 2 pops behave queue poll operations.
// s1: [3, 2, 1], s2: []
// pop() => s1: [2, 1], s2: [3]; s1: [1], s2: [2, 3]; and finally s1: [], s2: [1, 2, 3]
// now pop gives 1. Next pop gives 2 and so on. Do it still it becomes empty
// Once empty, again t/f all elements at once from stack 1 to stack 2 and do pop()
if(!stack2.isEmpty()) {
return stack2.pop();
} else {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
public int peek() {
// Same as pop
if(!stack2.isEmpty()) {
return stack2.peek();
} else {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
class Solution {
public static void main(String[] args) {
Solution s = new Solution();
MyQueue myQueue = new MyQueue();
myQueue.push(1);
myQueue.push(2);
System.out.println(myQueue.peek() == 1);
System.out.println(myQueue.pop() == 1);
System.out.println(myQueue.peek() == 2);
System.out.println(myQueue.pop() == 2);
System.out.println(myQueue.empty() == true);
}
}
🔑 Key Insights
- Pattern: Data Structure Transformation
- Magic: Transfer reverses order (LIFO→FIFO)
- Strategy: Lazy transfer (only when s2 empty)
- Optimization: Each element moves once
- Roles: s1=input, s2=output
- Time: push O(1), pop/peek Amortized O(1)
- Space: O(n)
🎪 Memory Aid
"Transfer reverses, lazy is best!"
"Stack1 input, Stack2 output, transfer when empty!" ✨
⚠️ Don't Forget
- Check
s2.isEmpty()before transfer - Check BOTH stacks in
empty() - Don't transfer back to s1
- Apply same logic for both
pop()andpeek()
🎉 Summary
The Problem: Queue (FIFO) using Stacks (LIFO)
The Insight: Transfer between stacks reverses order
The Strategy: - Stack1 for input - Stack2 for output - Lazy transfer (only when Stack2 empty)
Why Optimal: Each element moves at most once
Time: Amortized O(1) for all operations
Happy practicing! 🎯
Note: This is THE optimal solution for queue using stacks. The lazy transfer strategy ensures amortized O(1) - can't do better! Common at Amazon, Meta! 💪✨