A ticket printer’s work queue was supposed to fire jobs in arrival order. The firmware only exposed LIFO buffers. The intern reversed the whole inbox into a spare on every dequeue, printed the top, then reversed it back so the next enqueue still landed on the inbox. Ten jobs on a quiet shift were fine. A lunch rush made every ticket a linear pour on the hot path.

Implement Queue using Stacks asks for FIFO with two LIFO buffers. One stack already gives a cheap top. Pouring both ways on every dequeue 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 pairing two stacks so the oldest inbound value is the next pop.

The problem

Implement a FIFO queue using only two stacks. push(x) enqueues at the back. pop() dequeues and returns the front. peek() returns the front without removing it. empty() reports whether anything remains. You may only use stack operations: push to top, pop or peek from top, and is-empty.

A short session:

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

After two pushes the front is 1. After the first pop, 2 is still the front even though 3 just arrived.

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

Pour both ways is the honest brute force

Keep every value on an inbox stack. On pop or peek, dump inbox into a temp stack (that reverse puts the oldest value on top), take the front, then dump temp back onto inbox so the next push still lands on the same stack. Correct. Linear per dequeue.

class MyQueuePourBothWays {
    Deque<Integer> inbox = new ArrayDeque<>();
    Deque<Integer> temp = new ArrayDeque<>();

    void push(int x) {
        inbox.push(x);
    }

    int pop() {
        while (!inbox.isEmpty()) {
            temp.push(inbox.pop());
        }
        int front = temp.pop();
        while (!temp.isEmpty()) {
            inbox.push(temp.pop());
        }
        return front;
    }

    int peek() {
        while (!inbox.isEmpty()) {
            temp.push(inbox.pop());
        }
        int front = temp.peek();
        while (!temp.isEmpty()) {
            inbox.push(temp.pop());
        }
        return front;
    }

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

You can flip the bill and pour both ways on every push instead, so the front always sits on top and dequeue is cheap. Either way every operation that pours walks the whole queue. Interviewers let you say this out loud, then they want the pour that happens at most once per element.

Inbound for push, outbound for pop — pour only when the front is empty

inbound takes every push. outbound serves pop and peek. When outbound is empty, pour all of inbound onto outbound. That reverse happens once: the oldest remaining value lands on top of outbound and stays there until it is dequeued. If outbound still holds the current front, leave inbound alone — a new push is younger than everything already poured.

Each element moves from inbound to outbound at most once. That is why pop is amortized O(1).

Walk the session. Bottom is on the left; top is on the right.

push(1)  inbound [1]        outbound []
push(2)  inbound [1, 2]     outbound []
pop()    outbound empty → pour:
           inbound [1]      outbound [2]
           inbound []       outbound [2, 1]
         then pop outbound → 1
         inbound []         outbound [2]
push(3)  inbound [3]        outbound [2]
pop()    outbound not empty → do not pour
         pop outbound → 2
         inbound [3]        outbound []

If the second pop had poured because “inbound has new work”, 3 would land on top of 2 and you would dequeue 3 while 2 was still the front.

The Java is those two deques:

class MyQueue {
    Deque<Integer> inbound = new ArrayDeque<>();
    Deque<Integer> outbound = new ArrayDeque<>();

    void push(int x) {
        inbound.push(x);
    }

    int pop() {
        pourIfNeeded();
        return outbound.pop();
    }

    int peek() {
        pourIfNeeded();
        return outbound.peek();
    }

    boolean empty() {
        return inbound.isEmpty() && outbound.isEmpty();
    }

    private void pourIfNeeded() {
        if (outbound.isEmpty()) {
            while (!inbound.isEmpty()) {
                outbound.push(inbound.pop());
            }
        }
    }
}

Push is O(1). Pop and peek are amortized O(1) — each value is poured inbound→outbound at most once, so n operations cost O(n) pours in total. A single pop is worst-case O(n) when it triggers a pour. Space is O(n) for the two deques.

Note: Use Deque and ArrayDeque. java.util.Stack is a synchronized Vector leftover — not the ADT, not the interview type. empty() is true only when both deques are empty; a live front can sit on outbound while inbound is vacant, or a backlog can sit on inbound while outbound is vacant.

What interviewers usually poke next

  • Empty pop / peek. The prompt usually promises a non-empty queue. In production you would reject; at the board, ask.
  • Worst-case O(1) every call. Then you cannot hide a pour. Amortized O(1) is the usual contract; say the difference out loud.
  • Related design: Min Stack — two deques for a cheap extra op. Do not solve it here; the shared move is pairing two LIFO structures so the extra answer is already on a top.
  • Inverse: Implement Stack using Queues is a later problem. Same pairing, other direction; do not solve it here.
  • Recursion as the second stack. pop pours through the call stack instead of an explicit outbound deque. Cute, not the default; overflow is the cost. Mention it if they ask for one explicit stack, then go back to two deques.

You are done with this problem when you can say, out loud, why pouring both ways is correct, why you must not pour while outbound still holds the front, and why each element is poured at most once.