A handheld’s undo buffer was supposed to rewind the last tap first. The firmware only exposed FIFO work queues. The intern kept two queues and, on every undo, poured all but the last command into a spare, then took that leftover as the undo. A dozen taps in the lab were fine. A long configuration session made every undo a linear pour on the hot path.

Implement Stack using Queues asks for LIFO using only FIFO ends. One queue already gives a cheap front. Pouring all but the last value into a spare on every pop uses that and still pays linear time on the hot path.

This is an interview writeup, not a FIFO/LIFO lecture. The stack post owns push, pop, and why the top is the only cheap end. The queue post owns enqueue, dequeue, and why the front is the other cheap end. Here we only care about rotating a queue so the newest value is the next pop.

The problem

Implement a LIFO stack using only queue operations. push(x) puts x on the top. pop() removes and returns the top. top() returns the top without removing it. empty() reports whether anything remains. You may only use queue operations: offer to the back, poll or peek from the front, size, and is-empty.

A short session:

push(1)
push(2)
pop()   →  2
push(3)
pop()   →  3

After two pushes the top is 2. After the first pop, 1 remains. After push(3) the top is 3 — the newest — not 1.

Note: Empty pop / top is a contract question, not a design one. Ask whether the prompt promises a non-empty stack. At the board, do not invent a sentinel unless they ask.

Two queues, pour all but last is the honest brute force

Keep every value on a primary queue. On pop or top, offer-poll onto a spare until one leftover remains — the newest — then swap so primary holds what is left. Correct and linear per pop.

class MyStackPourAllButLast {
    Queue<Integer> primary = new ArrayDeque<>();
    Queue<Integer> spare = new ArrayDeque<>();

    void push(int x) {
        primary.offer(x);
    }

    int pop() {
        while (primary.size() > 1) {
            spare.offer(primary.poll());
        }
        int top = primary.poll();
        Queue<Integer> tmp = primary;
        primary = spare;
        spare = tmp;
        return top;
    }

    int top() {
        while (primary.size() > 1) {
            spare.offer(primary.poll());
        }
        int top = primary.peek();
        spare.offer(primary.poll());
        Queue<Integer> tmp = primary;
        primary = spare;
        spare = tmp;
        return top;
    }

    boolean empty() {
        return primary.isEmpty();
    }
}

You can skip the swap and pour the spare back onto primary after taking the last value — pour both ways, still linear. You can also flip the bill: on every push, offer onto an empty spare, pour primary onto that spare, then swap, so the newest already sits at the front and pop is a single poll. Either way every operation that pours walks the whole stack. Interviewers let you say this out loud, then they want the same rotation on one queue.

One queue: offer, then rotate until the newest is front

Use one ArrayDeque as a queue: offer at the back, poll / peek at the front. On push, offer the new value, then rotate size - 1 times — each rotate is offer(poll()), which takes the current front and sends it to the back. After those n - 1 moves, the value you just offered is the only one that has not been rotated, so it sits at the front. pop is poll. top is peek.

Walk the session. Front is on the left; back is on the right.

push(1)  offer 1                 [1]
push(2)  offer 2                 [1, 2]
         rotate n-1=1:
           poll 1, offer 1       [2, 1]
pop()    poll → 2                [1]
push(3)  offer 3                 [1, 3]
         rotate n-1=1:
           poll 1, offer 1       [3, 1]
pop()    poll → 3                [1]

If the second push had skipped the rotate because “the queue already holds work”, 3 would sit behind 1 and pop would return 1 while 3 was the real top.

The Java is that one queue:

class MyStack {
    Queue<Integer> q = new ArrayDeque<>();

    void push(int x) {
        q.offer(x);
        int n = q.size();
        for (int i = 0; i < n - 1; i++) {
            q.offer(q.poll());
        }
    }

    int pop() {
        return q.poll();
    }

    int top() {
        return q.peek();
    }

    boolean empty() {
        return q.isEmpty();
    }
}

Push is O(n) — every push rotates the values already in the queue. That is not amortized: unlike Queue Using Stacks, there is no “each element moves at most once.” A later push walks those same values again. Pop and top are O(1) — one poll or peek at the front. Space is O(n) for the deque.

Note: Use Queue and ArrayDeque. Stay on offer / poll / peek so the rotation is a queue rotation. Deque.push / Deque.pop would use the stack ends of the same array — that is cheating the prompt, not solving it. java.util.Stack is a synchronized Vector leftover — not the ADT, not the interview type, and not a queue.

What interviewers usually poke next

  • Empty pop / top. The prompt usually promises a non-empty stack. In production you would reject; at the board, ask.
  • Rotate on pop instead. push is a single offer (O(1)); pop and top rotate n - 1 so the oldest remaining value is not mistaken for the top. Same bill, other hot path. Say which end you paid.
  • Amortized O(1)? No. Queue-using-stacks defers a pour so each value moves inbound→outbound once. Stack-using-queues re-rotates the whole buffer on every new push. n pushes cost O(n²) rotations in total.
  • Inverse: Queue Using Stacks — two stacks, pour when the front is empty. Same pairing, other direction; do not re-solve it here.
  • Related design: Min Stack — two deques for a cheap extra op. Do not solve it here; the shared move is pairing structure so the extra answer is already on a cheap end.

You are done with this problem when you can say, out loud, why pouring all-but-last is correct, why rotate-on-push leaves the newest at the front, and why that push is O(n) every time rather than amortized.