232. Implement Queue using Stacks

Q: Why is the amortized complexity O(1) per op?

Aggregate analysis: n push/pop calls do at most 2n total stack operations because each element enters in-stack once, moves to out-stack at most once, and leaves out-stack at most once. Total work is O(n) for n queue operations.

Q: Why is the WORST-CASE pop still O(n)?

Because if you've pushed n elements and the out-stack is empty when you pop, that single pop call drains all n. The next n-1 pops are O(1) each, so the average is still O(1) — but the single worst pop is O(n).

easyAsked at Twilio

Implement Queue using Stacks is Twilio's amortized-analysis probe: build a FIFO queue using only stack primitives. The grading bar is whether you reach for the two-stack trick (in-stack + out-stack) and articulate the O(1) AMORTIZED guarantee on pop/peek.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Twilio loops.

Glassdoor (2026-Q1)— Listed in Twilio backend SWE phone-screen reports as a 'data-structure design' warm-up.
LeetCode Discuss (2025-12)— Cited in Twilio interview reports as a precursor to harder design questions.

Problem

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() returns true if the queue is empty. Amortized time complexity should be O(1) per operation.

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.

Examples

Example 1

Input

push(1), push(2), peek(), pop(), empty()

Output

[null, null, 1, 1, false]

Approaches

1. Single stack + reverse on every pop (rejected)

Push to a stack; on pop/peek, drain into a second stack to reverse, pop the top, drain back.

Time: push O(1), pop/peek O(n) every call
Space: O(n)

class MyQueueBrute {
  constructor() { this.s = []; }
  push(x) { this.s.push(x); }
  pop() {
    const tmp = [];
    while (this.s.length > 1) tmp.push(this.s.pop());
    const result = this.s.pop();
    while (tmp.length > 0) this.s.push(tmp.pop());
    return result;
  }
  peek() {
    const tmp = [];
    while (this.s.length > 1) tmp.push(this.s.pop());
    const result = this.s[0];
    while (tmp.length > 0) this.s.push(tmp.pop());
    return result;
  }
  empty() { return this.s.length === 0; }
}

Tradeoff: Drains the entire stack on every pop and re-drains it back — O(n) per call with O(n) extra ops. The optimal two-stack version amortizes this work.

2. Two stacks — in + out, lazy drain (optimal)

Push to in-stack. On pop/peek, if out-stack is empty, drain in-stack into out-stack. Pop from out-stack.

Time: amortized O(1) per op
Space: O(n)

class MyQueue {
  constructor() {
    this.in = [];
    this.out = [];
  }
  push(x) { this.in.push(x); }
  _drain() {
    if (this.out.length === 0) {
      while (this.in.length > 0) this.out.push(this.in.pop());
    }
  }
  pop() {
    this._drain();
    return this.out.pop();
  }
  peek() {
    this._drain();
    return this.out[this.out.length - 1];
  }
  empty() {
    return this.in.length === 0 && this.out.length === 0;
  }
}

Tradeoff: Each element moves from in to out exactly once over its lifetime, regardless of how many pop/peek calls happen. Amortized O(1): n operations do at most 2n stack pushes/pops total.

Twilio-specific tips

Twilio reviewers specifically want the amortized-analysis narration. State 'each element moves between stacks at most twice over its lifetime — once in, once out' BEFORE writing the code. The lazy drain (only when out is empty) is the entire amortization trick — preempt the interviewer's 'why don't you drain on every push?' question by explaining that it would push the work back to O(n) per push.

Common mistakes

Draining out-stack into in-stack on every push — defeats the amortization.
Not lazy-draining (always draining on pop even if out has items) — the next pop would also drain, double-paying.
Forgetting to handle empty() correctly — must check BOTH stacks, not just one.

Follow-up questions

An interviewer at Twilio may pivot to one of these next:

Can you also implement an stack using two queues (LC 225)? (Yes — opposite construction; one approach pushes everything through.)
What if push needed to be O(1) AMORTIZED but pop had to be O(1) WORST-CASE? (Doesn't exist with only stacks — need a deque.)
How would you make this thread-safe? (Lock the whole structure or use two separate locks with care to handle the drain-stage races.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the amortized complexity O(1) per op?

Aggregate analysis: n push/pop calls do at most 2n total stack operations because each element enters in-stack once, moves to out-stack at most once, and leaves out-stack at most once. Total work is O(n) for n queue operations.

Why is the WORST-CASE pop still O(n)?