Implement Stack with Queues

The problem

Implement a stack (push, pop, top, empty) using only queues.

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

Tradeoff

Queues give front easily; stacks need back. You pay O(n) on either push or pop.

Approach A — costly push (single queue)

On push: enqueue x, then rotate previous n elements behind x so x is at front.

class MyStack {
  private q: number[] = []; // front at index 0; use push/shift as queue

  push(x: number): void {
    this.q.push(x);
    for (let i = 0; i < this.q.length - 1; i++) {
      this.q.push(this.q.shift()!);
    }
  }

  pop(): number {
    return this.q.shift()!;
  }

  top(): number {
    return this.q[0];
  }

  empty(): boolean {
    return this.q.length === 0;
  }
}

op	time
push	O(n)
pop/top	O(1)* (*shift O(n) in JS array — speak to deque ideally)
empty	O(1)

Approach B — costly pop (two queues)

push to q1 O(1). pop: move all but last from q1→q2, pop last, swap names.

class MyStackTwoQ {
  private q1: number[] = [];
  private q2: number[] = [];

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

  pop(): number {
    while (this.q1.length > 1) this.q2.push(this.q1.shift()!);
    const v = this.q1.shift()!;
    [this.q1, this.q2] = [this.q2, this.q1];
    return v;
  }

  top(): number {
    while (this.q1.length > 1) this.q2.push(this.q1.shift()!);
    const v = this.q1[0];
    this.q2.push(this.q1.shift()!);
    [this.q1, this.q2] = [this.q2, this.q1];
    return v;
  }

  empty(): boolean {
    return this.q1.length === 0;
  }
}

Interview note on JS arrays

Real queues need O(1) front removal. In interviews, array + shift is usually accepted if you acknowledge cost. Prefer index-based queue if pressed.

Edge cases

• pop/top empty
• single element rotate
• interleaved ops

Common mistakes

• Rotating off-by-one (length vs length-1)
• Forgetting to swap queues
• Implementing stack with push/pop only and calling it queues

Interview delivery

1. State push-heavy vs pop-heavy design.
2. Implement one fully.
3. Complexities.
4. Optional two-queue variant.
5. JS shift caveat.

Mental model

Queues expose the oldest element; stacks need the newest. Rotate after each push so the newest sits at the front, or rotate on pop to expose the newest at the back. State the tradeoff up front.

Single vs dual queue

Single-queue rotate-on-push is easiest to code. Dual-queue move-on-pop is the textbook alternative. Either satisfies the problem.

Out-loud answer

“I’ll make push O(n): enqueue then rotate n-1 elements. Pop/top become O(1) at the front. Empty when queue empty. Mention JS array shift cost if relevant.”

Complexity table

Design	push	pop	top
Rotate on push (1 queue)	O(n)	O(1)*	O(1)*
Move on pop (2 queues)	O(1)	O(n)	O(n)

*ignoring JS shift cost

Interview delivery

1. State which op is O(n).
2. Implement rotate-on-push cleanly.
3. empty method.
4. Trace two pushes and a pop.
5. Mention dual-queue variant.

Related

• Implement Queue with Stacks
• Valid Parentheses
• Min Stack
• Daily Temperatures
• JavaScript Interview Guide

Further reading

• LeetCode 225 — Implement Stack using Queues
• MDN: Array shift/push