Implement Queue with Stacks

The problem

Implement a queue (push, pop, peek, empty) using only stacks.

push(1); push(2); peek() → 1; pop() → 1; empty() → false

Brute: one stack + rebuild

On every pop, reverse into a temp stack, pop front, reverse back. Correct O(n) per op. Mention as warm-up.

Optimal: two stacks (amortized O(1))

• inStack: receives pushes
• outStack: serves pops/peeks

When outStack is empty and we need front, pour all from in → out (reverses order → FIFO).

class MyQueue {
  private inStack: number[] = [];
  private outStack: number[] = [];

  push(x: number): void {
    this.inStack.push(x);
  }

  private move() {
    if (this.outStack.length === 0) {
      while (this.inStack.length) {
        this.outStack.push(this.inStack.pop()!);
      }
    }
  }

  pop(): number {
    this.move();
    return this.outStack.pop()!;
  }

  peek(): number {
    this.move();
    return this.outStack[this.outStack.length - 1];
  }

  empty(): boolean {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

op	amortized	worst
push	O(1)	O(1)
pop/peek	O(1)	O(n) when pouring
empty	O(1)	O(1)

Each element moves at most once in→out → amortized O(1).

Trace

push 1,2,3 → in=[1,2,3], out=[]
peek → pour → out=[3,2,1], peek 1
push 4 → in=[4]
pop → pop out → 1; out=[3,2]
pop → 2; pop → 3; pop → pour 4 → 4

Edge cases

• pop/peek on empty — constraints usually say won’t happen
• Alternating push/pop without full drain
• Single element

Common mistakes

• Pouring every push (defeats amortisation story if you pour both ways wrong)
• Pouring when out is non-empty (corrupts order)
• Using shift on a single array and calling it a stack

Interview delivery

1. Need reverse twice = queue.
2. Lazy transfer.
3. Never pour onto non-empty out.
4. Amortized analysis.
5. Implement cleanly.

Mental model

One stack reverses order. Two reverses restore FIFO. Lazy transfer means you only reverse when the output stack is dry, so each element moves O(1) times amortized.

Amortized proof (short)

Charge 2 tokens per push: one to enter in, one to later move to out. Pop spends the pre-paid move. No element is moved more than once in→out.

Out-loud answer

“Two stacks: in for push, out for pop/peek. When out is empty, pour in→out. Never pour onto non-empty out. Push O(1), pop amortized O(1). empty checks both.”

Complexity table

Operation	Amortized	Worst	Notes
push	O(1)	O(1)	only inStack
pop	O(1)	O(n)	pour when out empty
peek	O(1)	O(n)	same as pop without removing
empty	O(1)	O(1)	both stacks

Common bugs to avoid

• Pouring while outStack still has elements (interleaves epochs).
• Implementing peek via pop+push back incorrectly across two stacks.
• Forgetting empty must check both stacks.

Interview delivery

1. FIFO via double reverse.
2. Lazy pour.
3. Amortized analysis one sentence.
4. Code four methods.
5. Trace push/push/pop/push/pop.

Related

• Implement Stack with Queues
• Valid Parentheses
• Min Stack
• Evaluate Reverse Polish Notation
• JavaScript Interview Guide

Further reading

• LeetCode 232 — Implement Queue using Stacks
• Amortized analysis