225. Implement Stack using Queues

Q: How does rotate-on-push work?

After pushing x to the back, we dequeue and re-enqueue every OTHER element. The first such operation moves the original front to the back; the next moves the next-original-front to the back, and so on. After size-1 rotations, x is at the front.

Q: Why is the single-queue version preferred?

Same complexity, less state to track, simpler code. Apple grades simplicity at peers — given equal correctness, the simpler version wins.

easyAsked at Apple

Implement Stack using Queues is Apple's mirror to Queue-using-Stacks. The clever variant is one queue with rotate-on-push: after pushing x, dequeue and re-enqueue every existing element so x ends up at the front. Push becomes O(n); pop/top become O(1).

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 LC 225 alongside LC 232 as canonical data-structure design easies.
Blind (2025-11)— Apple new-grad reports cite Implement Stack using Queues as the recurring inversion question.

Problem

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the MyStack class: void push(int x) pushes element x to the top of the stack. int pop() removes the element on the top of the stack and returns it. int top() returns the element on the top of the stack. boolean empty() returns true if the stack is empty, false otherwise. Notes: You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

Constraints

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

Examples

Example 1

Input

["MyStack","push","push","top","pop","empty"]
[[],[1],[2],[],[],[]]

Output

[null,null,null,2,2,false]

Approaches

1. One queue with rotate-on-push (optimal)

After enqueueing x, rotate the queue: dequeue then enqueue every OTHER element. Now x is at the front.

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

class MyStack {
  constructor() {
    this.q = [];
  }
  push(x) {
    this.q.push(x);
    for (let i = 0; i < this.q.length - 1; i++) {
      this.q.push(this.q.shift());
    }
  }
  pop() {
    return this.q.shift();
  }
  top() {
    return this.q[0];
  }
  empty() {
    return this.q.length === 0;
  }
}

Tradeoff: Single queue. After every push, the queue is in stack order (newest at front). All other ops are O(1). Apple's preferred answer because it uses a single queue.

2. Two queues with O(n) push

Push to q2, drain q1 onto q2, swap q1 and q2.

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

class MyStack {
  constructor() { this.q1 = []; this.q2 = []; }
  push(x) {
    this.q2.push(x);
    while (this.q1.length) this.q2.push(this.q1.shift());
    [this.q1, this.q2] = [this.q2, this.q1];
  }
  pop() { return this.q1.shift(); }
  top() { return this.q1[0]; }
  empty() { return this.q1.length === 0; }
}

Tradeoff: Two queues, same complexity. Apple grades the single-queue version higher because it shows you noticed the second queue is redundant.

3. Two queues with O(n) pop

Push to q1 directly. On pop, drain q1 to q2 leaving last, return that last; swap.

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

// q1 is the holding queue, q2 is the scratch. On pop, move n-1 elements to q2 then return the remaining.
// Apple prefers the O(n) push version because pop is the more common op.

Tradeoff: Symmetric to O(n) push; pick whichever side you want to make slower. The constraint mentions <=100 calls so either passes.

Apple-specific tips

Apple's grade here is on whether you reach the SINGLE-queue version. Two queues with O(n) push works but is the obvious answer. Saying 'I can do this with one queue' and writing the rotate-on-push is the bonus that separates good from great. Walk through push(1), push(2), push(3) on the whiteboard: after each push the queue front is the most recent.

Common mistakes

Using both queues when one suffices.
Off-by-one in the rotation loop — should rotate size-1 elements, not size.
Forgetting to maintain the front-is-top invariant on pop (pop just dequeues, which is already correct because of how push set it up).

Follow-up questions

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

Implement Queue using Stacks (LC 232) — the inverse.
Min Stack (LC 155) — stack with O(1) min query, different structure.
What if you could use ONLY one queue with no scratch space?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

How does rotate-on-push work?

After pushing x to the back, we dequeue and re-enqueue every OTHER element. The first such operation moves the original front to the back; the next moves the next-original-front to the back, and so on. After size-1 rotations, x is at the front.

Why is the single-queue version preferred?

Same complexity, less state to track, simpler code. Apple grades simplicity at peers — given equal correctness, the simpler version wins.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Implement Stack using Queues 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 →