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 Alex Chen, 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)?

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).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Implement Queue using Stacks and other Twilio interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →