Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.

Two stacks, one reversal

A stack hands back the most recent arrival and a queue hands back the oldest, so the whole construction is about applying exactly one order reversal, at the right moment.

Keep an inbound stack and an outbound stack. Enqueue pushes onto inbound and does nothing else. Dequeue pops from outbound. When outbound is empty and a dequeue arrives, pop every element from inbound and push each onto outbound: the pops come off in newest-first order and the pushes stack them so the oldest ends up on top. One reversal, and outbound is now in queue order.

The invariant to state is that outbound holds a prefix of the queue in the correct order, inbound holds the remaining suffix in reverse, and the front of the queue is the top of outbound whenever outbound is non-empty.

Refilling early reverses the queue

The guard on the transfer is the only subtle thing here, and it is easy to write the version without it because that version passes the first test you think of.

Enqueue 1 and 2. Inbound holds 1 then 2 with 2 on top; outbound is empty. Dequeue: outbound is empty, so transfer, giving outbound with 1 on top and 2 beneath. Pop returns 1, correctly. Outbound still holds 2.

Now enqueue 3, so inbound holds 3 alone, and dequeue again. The correct answer is 2. If the transfer runs unconditionally, 3 is popped from inbound and pushed onto outbound on top of 2, so outbound now has 3 on top and the dequeue returns 3. The queue has served 1 then 3 and will serve 2 last. That is not a subtle ordering difference, it is not a queue at all, and it only appears once you interleave an enqueue between two dequeues — which is precisely the pattern a two-operation test never produces.

The rule is that inbound may only be emptied into outbound when outbound is completely empty. Half-transfers and top-ups are both wrong for the same reason: they interleave a newer element into a run of older ones.

class QueueFromStacks<T> {
    private final Deque<T> inbound = new ArrayDeque<>();
    private final Deque<T> outbound = new ArrayDeque<>();

    void enqueue(T value) {
        inbound.push(value);
    }

    T dequeue() {
        shiftIfNeeded();
        return outbound.pop();
    }

    T peek() {
        shiftIfNeeded();
        return outbound.peek();
    }

    int size() {
        return inbound.size() + outbound.size();   // no transfer needed to answer this
    }

    private void shiftIfNeeded() {
        if (!outbound.isEmpty()) return;            // the guard: only ever refill from empty
        while (!inbound.isEmpty()) outbound.push(inbound.pop());
    }
}

Amortised constant, derived rather than quoted

Follow one element through its entire life. It is pushed onto inbound once. It is popped from inbound at most once, during exactly one transfer. It is pushed onto outbound at most once. It is popped from outbound at most once, when it is served. Four stack operations, each constant time, and no element can ever be transferred twice because an element only moves in one direction and outbound is never drained back.

So a sequence of n enqueues and n dequeues performs at most 4n stack operations in total, which is O of 1 per operation amortised. That derivation is the answer the question wants. Quoting "amortised O of 1" without it is the difference between having read the result and being able to produce it, and the interviewer will usually ask you to justify it anyway.

The honest qualification is that the worst case for a single dequeue is O of n, because the dequeue that triggers a transfer of n elements pays for all of them at once. Amortised and worst-case bounds answer different questions, and which one you need depends on the caller. For a batch consumer that only cares about total throughput, the amortised bound is the relevant one. For anything with a per-operation latency budget, a single dequeue that stalls for the length of the queue is a real problem, and the answer there is a different structure — a circular buffer, or a linked queue with head and tail pointers — rather than a cleverer transfer schedule. Any scheme that spreads the transfer out has to keep both stacks partially populated, which is exactly what the ordering argument above forbids.

Where this is not a puzzle

The construction has a genuine home in purely functional programming, where you cannot mutate a structure in place and a queue therefore has to be built out of immutable lists. A pair of lists, one holding the front in order and one holding the rear reversed, with the rear reversed onto the front when the front runs out, is the standard functional queue and is exactly this algorithm. Okasaki's work on purely functional data structures analyses it in detail, including the awkward point that naive amortised analysis is not valid when a persistent structure can be used more than once from the same intermediate state.

That last point is the best available answer to the follow-up about threads. Two threads sharing this queue break it in the ordinary way, through unsynchronised access to two collections that must be updated together, but they also break the amortised argument itself: if two dequeues can both observe an empty outbound stack, both may perform the transfer, and the cost accounting that assumed each element moves once no longer holds.