Queue Using Stacks | Data Structure Design | Stack

Overview

Queue using stacks: implement FIFO (push to back, peek/pop from front) using only stack operations. Use two stacks: inStack (for push) and outStack (for pop/peek). Push always goes to in. For pop/peek, if out is empty, flush in into out (pop from in, push to out — reverses order); then pop or peek from out. Amortized O(1) per operation because each element is pushed and popped at most twice.

When to Use

FIFO with stack-only APIs — e.g. language or library only exposes stacks.
BFS/level-order when you only have a stack — simulate queue with two stacks.
Reversing in chunks — similar in/out transfer pattern.

How It Works

inStack holds elements in arrival order (newest on top). outStack holds them in reverse (oldest on top). Flush moves all from in to out only when out is empty, so the front of the queue is always at the top of out.

Example 1: Two Stacks (Standard)

class MyQueue {
  private in: number[] = [];
  private out: number[] = [];
  push(x: number): void { this.in.push(x); }
  pop(): number {
    this.flush();
    return this.out.pop()!;
  }
  peek(): number {
    this.flush();
    return this.out[this.out.length - 1];
  }
  private flush(): void {
    if (this.out.length === 0)
      while (this.in.length > 0) this.out.push(this.in.pop()!);
  }
  empty(): boolean { return this.in.length === 0 && this.out.length === 0; }
}

Amortized: O(1) per push, pop, peek. Space: O(n).

Example 2: Amortized Analysis

Each element is pushed once to in, moved at most once to out (one pop from in, one push to out), and popped once from out. So 2 pushes and 2 pops per element over its lifetime. Over n operations, total work is O(n) → amortized O(1) per operation.

Example 3: Step-by-Step Trace

push(1): in=[1], out=[]. push(2), push(3): in=[1,2,3], out=[]. pop(): flush → in=[], out=[3,2,1]; pop → return 1; out=[3,2]. pop(): return 2; out=[3]. push(4): in=[4], out=[3]. pop(): return 3; out=[]. pop(): flush → in=[], out=[4]; return 4. empty(): true.

Example 4: size() in O(1)

Maintain a counter: increment on push, decrement on pop. Or compute size as in.length + out.length (no extra field).

size(): number { return this.in.length + this.out.length; }

Example 5: Edge Cases

Empty pop/peek: flush does nothing when in is also empty; out stays empty. Document that pop/peek are undefined when empty (or throw).
Single element: push(1); peek() flushes 1 to out, returns 1; pop() returns 1; empty() true.
Alternating push-pop: push(1), pop() → flush then pop; push(2), pop() → out already has nothing, flush moves 2 to out, pop returns 2. Correct FIFO.

Summary

Queue from two stacks: in (push), out (pop/peek); flush in → out when out is empty. Amortized O(1). See Stack Basics.

Implement Queue using Stacks