Implement Stack using Queue

The problem, simply

Build a stack, a pile where the last thing in is the first thing out. It needs push(x), pop(), top() and empty().

The catch: inside, you may only use queues. A queue is a fair waiting line. You can only add people at the back, look at or remove the person at the front, and ask for the size. The line gives back the oldest person first, but a stack must give back the newest. You have to flip that order somehow.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use two lines: the main line q1 and a helper line q2. Keep q1 in newest first order at all times.

1. push(x): move everybody from q1 into q2.
2. Put x into the now empty q1. It is alone, so it is at the front.
3. Move everybody from q2 back into q1, behind x.
4. pop() and top() use the front of q1.

import java.util.*;

class MyStack {
    private Queue<Integer> q1 = new ArrayDeque<>();   // main line, newest at the front
    private Queue<Integer> q2 = new ArrayDeque<>();   // helper line

    public void push(int x) {
        while (!q1.isEmpty()) q2.offer(q1.poll());    // everybody steps aside
        q1.offer(x);                                  // the new kid stands first
        while (!q2.isEmpty()) q1.offer(q2.poll());    // everybody comes back behind
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

How long it takes: each push moves all n items twice, so it is O(n). pop, top and empty are O(1). Extra room: the two lines together hold n items, O(n).

Way 2: the clever way

You do not need the helper line. One line can rotate itself, just like the polite lunch line.

1. push(x): remember the size before x arrives. Call it k.
2. Add x at the back.
3. k times: take the front person and add them at the back. Now x is at the front.
4. pop(): remove the front. top(): peek at the front.

import java.util.*;

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

    public void push(int x) {
        int k = q.size();          // how many were here before x
        q.offer(x);                // x joins at the back
        for (int i = 0; i < k; i++) {
            q.offer(q.poll());     // each older one walks to the back
        }
    }

    public int pop() {
        if (q.isEmpty()) throw new RuntimeException("stack is empty");
        return q.poll();           // the front is the newest
    }

    public int top() {
        if (q.isEmpty()) throw new RuntimeException("stack is empty");
        return q.peek();
    }

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

How long it takes: push rotates the n older items once, O(n). pop, top and empty are O(1). Extra room: one line of n items, O(n), and no helper line. Same speed as Way 1 but half the moving and only one queue.

Another way: cheap push, costly pop

You can also flip the deal. Let push be a plain offer, and do the rotating when someone asks for the top.

import java.util.*;

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

    public void push(int x) {
        q.offer(x);                          // O(1)
    }

    public int pop() {
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());               // bring the newest to the front
        }
        return q.poll();
    }

    public int top() {
        int x = pop();                       // find the newest
        q.offer(x);                          // put it back at the back, where the newest lives
        return x;
    }

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

Here push is O(1) and pop and top are O(n). Pick this one when pushes happen much more often than pops.

Watch out for

• Calling pop() or top() on an empty stack. poll() returns null, which crashes when unboxed to int.
• In the cheap push version, top() must put the item back at the back of the line, because the back is where the newest item lives in that version.
• Using q.size() as the loop bound while the loop changes the queue. In the code above the size stays the same during a rotation, but read it once if in doubt.

What interviewers ask next

• Can both push and pop be O(1) with only queues? No. A queue never changes the order of its items, so someone must pay to reverse the order. One of the two moves costs O(n).
• Build a queue from two stacks, the reverse problem. Push into an "in" stack, and when the "out" stack is empty, pour everything across. Each item moves at most twice, so it is O(1) on average.
• Which version do you pick? If the program pushes a lot and rarely pops, use cheap push. If it reads the top a lot, use cheap pop, which is Way 2.
• What does ArrayDeque cost? offer, poll and peek are O(1) on average, so the cost of each version comes only from the rotations.

Remember this

Grown-up words: the waiting line is a queue (first in, first out), the pile is a stack (last in, first out), joining at the back is offer, leaving the front is poll, and walking from front to back is a rotation.