LeetCode · #232

Implement Queue using Stacks Solution

Use two stacks and lazy transfer to simulate FIFO behavior with amortized O(1) queue operations.

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #232

🏗️

Pattern

Design — Two Stacks

Implement a FIFO queue using only standard stack operations: push, pop, top/peek, size, and empty.

Example

 MyQueue q = new MyQueue();
q.push(1);
q.push(2);
q.peek(); // 1
q.pop(); // 1
q.empty(); // false 

Section Two · Brute Force

Expensive Push

Keep all queue elements in one stack with the front always on top. On every push, move everything to a helper stack, add the new element, then move everything back.

Problem: This makes every push O(n). We can do better by delaying reversals until they are actually needed.

Section Three · Optimal

Two Stacks + Lazy Transfer

Use one stack for incoming elements and one for outgoing elements:

inStack: new pushes go here
outStack: pops and peeks come from here

When outStack is empty and you need the front, pour all elements from inStack into outStack. That reversal restores FIFO order.

💡 Mental model: Think of inStack as arrivals and outStack as the departure gate. You only move everyone from arrivals to departures when the departure gate runs empty.

Why amortized O(1)?:

Every element moves from inStack to outStack at most once.
So even though one transfer step can cost O(n), the total cost spread across operations is linear.

Section Four · Walkthrough

Visual Walkthrough

Lazy transfer only when needed

Section Five · Code

Code — Java & Python

Java — two stacks (using ArrayDeque)

 import java.util.ArrayDeque;
import java.util.Deque;
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>();
private final Deque<Integer> out = new ArrayDeque<>();
public void push(int x) {
        in.push(x);
    }
private void moveIfNeeded() {
if (!out.isEmpty()) return;
while (!in.isEmpty())
            out.push(in.pop());
    }
public int pop() {
moveIfNeeded();
return out.pop();
    }
public int peek() {
moveIfNeeded();
return out.peek();
    }
public boolean empty() {
return in.isEmpty() && out.isEmpty();
    }
}

Python — two stacks

 class MyQueue:
def __init__(self):
        self.ins = []
        self.outs = []
def push(self, x: int) -> None:
        self.ins.append(x)
def _move_if_needed(self):
if self.outs:
return while self.ins:
            self.outs.append(self.ins.pop())
def pop(self) -> int:
        self._move_if_needed()
return self.outs.pop()
def peek(self) -> int:
        self._move_if_needed()
return self.outs[-1]
def empty(self) -> bool:
return not self.ins and not self.outs

Section Six · Analysis

Complexity Analysis

Approach	Push	Pop / Peek	Space
Expensive push	O(n)	O(1)	O(n)
Two stacks + lazy transfer	O(1)	O(1) amortized	O(n)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	What happens	Why it matters
Many pushes before first pop	One bulk transfer happens later	This is where amortized analysis matters.
Alternating push/pop	Still correct	`out` only refills when empty.
Single element queue	`peek()` and `pop()` both return that element	The transfer logic must handle tiny cases too.

⚠ Common Mistake: Transferring from in to out on every pop or peek. Only transfer when out is empty; otherwise you lose the amortized O(1) benefit.

← Back to Deque practice

LearningTree

LC 232 · Implement Queue using Stacks — Solution & Explanation | DSA Guide