225. Implement Stack using Queues
easyAsked at AppleImplement Stack using Queues is the design-inversion easy that Apple candidates report as the mirror image of Queue-using-Stacks. The graded insight is the single-queue rotate-on-push variant: after enqueueing x, dequeue and re-enqueue every existing element so x lands at the front — push becomes O(n) while pop and top stay O(1), and the second queue turns out to be entirely redundant.
By Sam K., Founder, InterviewChamp.AI · Last verified
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 <= 9At most 100 calls will be made to push, pop, top, and empty.All the calls to pop and top are valid.
Examples
Example 1
["MyStack","push","push","top","pop","empty"]
[[],[1],[2],[],[],[]][null,null,null,2,2,false]Explanation: After push(1), push(2) with rotation, the queue reads [2,1] — newest at the front. top and pop both see 2, and after the pop one element remains so empty is false.
Example 2
push(1), push(2), push(3) — queue state trace[1] -> [2,1] -> [3,2,1]Explanation: The whiteboard trace interviewers ask for: each push rotates the prior elements behind the newcomer, so the queue's front-to-back order always equals the stack's top-to-bottom order.
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.
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.
Can both push AND pop be O(1) using queues?
No — a queue only exposes FIFO order, so SOME operation must spend O(n) reversing that order to fake LIFO. The freedom you have is choosing WHICH operation pays: rotate-on-push makes reads cheap, drain-on-pop makes writes cheap. Saying that trade out loud is the senior answer.
Free learning resources
Curated free links for this problem.