232. Implement Queue using Stacks

Q: Why amortized and not worst-case O(1)?

A single pop can trigger a full drain of inStack to outStack, which is O(n). But each element only experiences this once across its lifetime in the queue. Over k operations the total work is O(k), so per-op it's O(1) amortized.

Q: Could we use a single stack?

Not without violating the 'only stack ops' constraint. You'd need to use the call stack via recursion (which is technically a stack but borrowing it from the language).

easyAsked at Apple

Implement Queue using Stacks is Apple's classic 'reverse the access pattern' design easy. Two stacks — one for input, one for output. The trick is the amortized O(1) pop: only move from input to output when output is empty, so each element moves at most once.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Apple loops.

Glassdoor (2026-Q1)— Apple SWE phone-screen reports list this and its inverse (LC 225) as canonical data-structure design easies.
Blind (2025-11)— Apple new-grad reports cite Implement Queue using Stacks as the canonical amortized-analysis easy.

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, false otherwise. Notes: You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

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

["MyQueue","push","push","peek","pop","empty"]
[[],[1],[2],[],[],[]]

Output

[null,null,null,1,1,false]

Explanation: Push 1, push 2, peek returns 1 (front), pop returns 1, empty returns false.

Approaches

1. Two stacks with lazy transfer (optimal amortized O(1))

inStack for push, outStack for pop/peek. When outStack is empty during pop or peek, drain all of inStack onto outStack first.

Time: Amortized O(1) per operation
Space: O(n)

class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  push(x) {
    this.inStack.push(x);
  }
  _shift() {
    if (this.outStack.length === 0) {
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
    }
  }
  pop() {
    this._shift();
    return this.outStack.pop();
  }
  peek() {
    this._shift();
    return this.outStack[this.outStack.length - 1];
  }
  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

Tradeoff: Each element is pushed once to inStack, popped from inStack once, pushed to outStack once, popped from outStack once — 4 ops total per element across its lifetime. So amortized O(1) per queue operation. Apple grades on whether you can articulate this amortized bound.

2. Two stacks with eager transfer (O(n) per push)

On push, drain outStack onto inStack, push x onto outStack, then drain inStack back onto outStack — keeping outStack always in queue order.

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

// Push moves everything to inStack, pushes x to outStack, moves everything back.
// Pop is just outStack.pop().
// Strictly worse amortized than lazy transfer.

Tradeoff: Worst-case O(1) on pop/peek but O(n) on every push. The lazy version is strictly better amortized.

Apple-specific tips

Apple is grading the AMORTIZED analysis. Say it out loud: 'each element is pushed to inStack, transferred to outStack, popped from outStack — three operations across its lifetime. So 100 push/pop pairs do 300 ops total, which is amortized O(1) per call.' Apple specifically rewards candidates who can name the amortized bound without prompting.

Common mistakes

Transferring inStack to outStack on EVERY pop instead of only when outStack is empty — destroys the amortized bound.
Forgetting that empty() must check BOTH stacks.
Confusing the two stacks — inStack holds newest at top, outStack holds oldest at top.

Follow-up questions

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

Implement Stack using Queues (LC 225) — the inverse, one of the queues has to do the work.
What if peek/pop were called way more often than push? Eager transfer might win.
How would you make the queue thread-safe?

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 amortized and not worst-case O(1)?

A single pop can trigger a full drain of inStack to outStack, which is O(n). But each element only experiences this once across its lifetime in the queue. Over k operations the total work is O(k), so per-op it's O(1) amortized.

Could we use a single stack?

Not without violating the 'only stack ops' constraint. You'd need to use the call stack via recursion (which is technically a stack but borrowing it from the language).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →