#225 Implement Stack using Queues

frequently reported atBloomberg Microsoft Amazon

the problem

In plain words

Build a LIFO stack (push, pop, top, empty) using only standard queue operations: push to back, peek/pop from front, size and isEmpty.

in push(1), push(2), top(), pop(), empty()

out 2, 2, false

1 ≤ x ≤ 9
At most 100 calls
pop and top are always valid
Follow-up: use only one queue

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack & queue design

A queue can't reverse itself, but it can rotate: poll from the front and offer to the back. Rotate n−1 times after a push and the newest element reaches the front.

solutions

From brute force to optimal

Push is a plain offer. To pop, move all but the last element to a helper queue, take the last one, then swap the queues.

push: main.offer(x).
pop: move size − 1 elements to helper; poll the remaining one; swap main and helper.
top: pop, then push the value back.

timepush O(1), pop/top O(n)

Each pop moves n − 1 elements.

spaceO(n)

Elements are split between the two queues.

javajava.util.*

1// On LeetCode, name this class MyStack.2class MyStackTwoQueues {3    private Queue<Integer> main = new ArrayDeque<>();4    private Queue<Integer> helper = new ArrayDeque<>();5 6    public void push(int x) {7        main.offer(x); // O(1): newest goes to the rear8    }9 10    public int pop() {11        while (main.size() > 1) helper.offer(main.poll()); // move all but the newest12        int top = main.poll(); // the newest is the only one left13        Queue<Integer> t = main; // swap roles so main holds the rest again14        main = helper;15        helper = t;16        return top;17    }18 19    public int top() {20        int x = pop(); // reuse pop...21        push(x); // ...and put it back as the newest22        return x;23    }24 25    public boolean empty() {26        return main.isEmpty();27    }28}

After offering x, rotate the older n − 1 elements behind it so the front is always the top of the stack.

push: offer x, then size − 1 times do q.offer(q.poll()).
pop: q.poll().
top: q.peek().

timepush O(n), pop/top O(1)

Each push rotates n − 1 elements; reading the front is O(1).

spaceO(n)

One queue of n elements — and no second queue, which answers the follow-up.

javajava.util.*

1class MyStack {2    private final Queue<Integer> q = new ArrayDeque<>(); // front = top of the stack3 4    public void push(int x) {5        q.offer(x);6        for (int i = 0; i < q.size() - 1; i++) {7            q.offer(q.poll()); // rotate older elements behind x, so x reaches the front8        }9    }10 11    public int pop() {12        return q.poll();13    }14 15    public int top() {16        return q.peek();17    }18 19    public boolean empty() {20        return q.isEmpty();21    }22}

in the room

How to say it in the interview

talk track

Ask which operation should be cheap — you can make push O(1) or pop O(1), not both.
The one-queue rotation is the cleanest answer; mention the two-queue version as the alternative.

traps

Rotating size times instead of size − 1 — x goes back to the rear.

what they ask next

Follow-ups

Which is better in practice?

Neither — a real stack is ArrayDeque.push/pop. This problem tests whether you understand both orders.

before you submit

Edge cases to test

One element: push, then top and pop return it, and empty becomes true.
Pushes between pops: each push rotates only the older elements (size − 1 of them), never itself.
top twice in a row returns the same value and removes nothing.

practise next