Implement Queue using Stack

The problem, simply

Build a queue, a first in first out line, but you may only use stacks inside it. A stack can only push, pop, peek at the top, and say if it is empty.

You need push(x) to add at the back, pop() to remove from the front, peek() to see the front, and empty().

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep the whole line in one stack with the front on top. To push a new value at the back, it has to go to the bottom. So pour everything into the second stack, push the new value, and pour everything back.

1. push(x): move all of s1 into s2, push x onto s1, move all of s2 back onto s1.
2. pop() and peek(): use the top of s1.

class MyQueue {
    private final Deque<Integer> s1 = new ArrayDeque<>();   // front on top
    private final Deque<Integer> s2 = new ArrayDeque<>();

    public void push(int x) {
        while (!s1.isEmpty()) s2.push(s1.pop());   // pour out
        s1.push(x);                                // x goes to the bottom
        while (!s2.isEmpty()) s1.push(s2.pop());   // pour back
    }

    public int pop() { return s1.pop(); }

    public int peek() { return s1.peek(); }

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

How long it takes: each push moves all n values twice, O(n). Pop and peek are O(1). Extra room: the two stacks hold n values together, O(n).

Way 2: the clever way

Use the two cups. The in stack takes new values. The out stack hands out old values.

1. push(x): push onto in. Nothing else.
2. pop() or peek(): if out is empty, pour all of in onto out. The order flips, so the oldest value ends up on top. Then pop or peek out.
3. empty(): both stacks are empty.

Only pour when out is empty. Values already in out are older than anything in in, so they must leave first.

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();    // new values
    private final Deque<Integer> out = new ArrayDeque<>();   // oldest on top

    public void push(int x) {
        in.push(x);
    }

    public int pop() {
        pourIfNeeded();
        return out.pop();
    }

    public int peek() {
        pourIfNeeded();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }

    private void pourIfNeeded() {
        if (out.isEmpty()) {                       // only when out has run dry
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

How long it takes: one pop can pour n values, which is O(n) for that call. But each value is poured at most once in its life, so over any run of m actions the total work is O(m). That is O(1) amortized per action. Extra room: O(n) for the values.

Watch out for

• empty() must check both stacks. Values may be waiting in in while out is empty.
• peek() needs the same pour as pop(). Peeking at in gives the newest value, not the oldest.
• Amortized is not the same as worst case. A single pop can still take O(n). If the interviewer needs a strict O(1) per call, say so and discuss it.

What interviewers ask next

• Why is it amortized O(1)? Each value goes through four steps: push to in, pop from in, push to out, pop from out. Four steps per value means O(m) total for m pushes.
• Build a stack from queues instead. Use one queue: after each push, rotate the older values behind the new one, so the newest is at the front. Push becomes O(n).
• Do it with one stack and recursion. Push stays normal; to pop the bottom, pop down recursively and push back on the way out. The call stack is the second stack.
• Make a queue that can return its minimum in O(1). Use two min stacks in this same design.
• Where is this used? Functional languages build queues out of two immutable lists in exactly this way.

Remember this

Grown-up words: the cups are stacks, the line is a queue (first in first out), pouring is transferring, and "fast on average even if one call is slow" is amortized O(1).