In a queue built from two stacks, when may elements move from the inbound to the outbound stack?
answer
- think about what the outbound stack still holds
- two stacks, but only one exit
- reversal is only valid on a clean surface
- newer items must never land above older
- guard the transfer with an emptiness check
basics
~20 sOnly when the outbound stack is empty. Pushing the inbound stack's contents onto a non-empty outbound stack puts newer arrivals above older ones and destroys first-in-first-out order. Standard implementations drain the inbound stack completely in that one transfer.
solid answer
~40 sThe construction keeps two stacks: every enqueue pushes onto the inbound stack, every dequeue pops from the outbound stack. The outbound stack is refilled by popping the inbound stack and pushing each element across — one pass that reverses the order, so the oldest element ends up on top. That reversal is only valid on an empty outbound stack. If elements still sit there, the newly transferred ones land on top of them and are returned first, so a later arrival overtakes an earlier one. So the rule is a guard, not an optimisation: `if outbound is empty, move everything across`. The queue is empty only when both stacks are empty, and a peek uses the same guarded transfer before reading the outbound top.
code
pseudocode · 10 linesenqueue(x):
push(inbound, x)
dequeue():
if isEmpty(outbound):
while not isEmpty(inbound):
push(outbound, pop(inbound))
if isEmpty(outbound):
error "queue is empty"
return pop(outbound)go deeper
Be ready to say what each of the two stacks is for and to state the one rule that keeps order correct: refill the outbound stack only when it is empty.
Explain the reversal itself — popping one stack and pushing onto another flips the order — and trace a mixed sequence of additions and removals to show exactly where an early transfer corrupts it.
Expect questions about where the emptiness and peek checks live, and point out that the guard is what batches one linear pass across many cheap removals instead of paying it per call.
Own the framing that this construction trades a smooth per-operation cost for a cheap total cost, and say which workloads tolerate that and which need per-operation bounds instead.
## The construction A stack returns the element pushed most recently; a queue must return the element added least recently. Building the second from two of the first works by exploiting a simple fact: **popping one stack and pushing each element onto another reverses the order**. One reversal is exactly the distance between last-in-first-out and first-in-first-out. So keep two stacks. Call them **inbound** and **outbound**. - **Enqueue**: push onto inbound. Always. Constant time, no conditions. - **Dequeue**: if outbound is empty, pop everything off inbound and push it onto outbound; then pop outbound. ## Why the reversal produces the right order Suppose `a` then `b` then `c` are enqueued. Inbound holds them with `c` on top. Popping inbound yields `c`, `b`, `a` — newest first. Pushing each onto outbound therefore leaves `a` on top, `b` beneath it, `c` at the bottom. Popping outbound now yields `a`, `b`, `c` — the arrival order. One pass, and the ordering is fixed. ## Why the guard is a correctness rule The usual first implementation transfers whenever the dequeue feels like it, and it breaks the moment enqueues and dequeues interleave. Trace it: 1. Enqueue `a`, `b`. Inbound (bottom to top): `a, b`. 2. Dequeue: outbound is empty, so transfer. Outbound (bottom to top): `b, a`. Pop returns `a`. Outbound now holds `b`. 3. Enqueue `c`, `d`. Inbound holds `c, d`. 4. Dequeue **with an unguarded transfer**: pop `d` and push, pop `c` and push. Outbound is now `b, d, c` from bottom to top. The pop returns `c`. The queue has now returned `a` then `c`, skipping `b` entirely, and will return `d` before `b`. Correct order was `a, b, c, d`. The corruption is not a rounding error in the cost; it is a wrong answer. The guard — transfer *only* into an empty outbound stack — is what makes the invariant hold: **outbound always contains a contiguous prefix of the queue, in order, and inbound always contains the elements that arrived after all of them, in reverse.** ## The operations that people forget - **Emptiness**: the queue is empty exactly when *both* stacks are empty. Testing only outbound reports an empty queue while items are waiting in inbound. - **Peek / front**: run the same guarded transfer, then read (do not pop) the outbound top. Peek is not a read-only operation in this design — it can trigger the transfer — which surprises people who assume a query never mutates internal state. - **Size**: the sum of both stacks' sizes. ## Cost, briefly Enqueue is constant time. A dequeue is constant time when outbound is non-empty and linear in the number of moved elements when it is not. Because each element crosses over exactly once in its lifetime, the cost spread over a sequence of operations stays constant per operation — that amortised argument is a subject of its own and is worth being able to defend out loud. ## The design that does *not* work well, and why it is instructive You could insist that dequeue is *always* constant time by keeping everything in outbound in queue order at all times. Then every enqueue has to move the whole outbound stack to inbound, push the new element, and move it all back — a linear cost on every enqueue, with no reuse and nothing to amortise. Comparing the two designs shows what the guard actually buys: it batches the reversal so that one expensive pass serves many later cheap pops, instead of redoing the same work on every call. ## Where the idea generalises The pattern here is **lazy batched reversal**: keep new work in a cheap staging area, and pay to reorganise it only when the consuming side runs dry. It is the same shape as any "accumulate, then flush" design, and interviewers reach for this construction precisely because it makes that shape small enough to reason about in five minutes.
- How do you correctly answer 'is this queue empty?' in this design?Both stacks must be empty. Checking the outbound stack alone reports an empty queue whenever every pending element is still sitting in the inbound stack awaiting its transfer — a common bug, because the check passes in the simple test where all enqueues precede all dequeues and fails as soon as the two interleave.
- Can peek be implemented without mutating anything?Not without giving something up. Peek must return the oldest element, which lives at the bottom of the inbound stack when the outbound stack is empty, so it has to trigger the same guarded transfer. That makes a nominally read-only query a state-changing operation, which matters if several readers share the structure or if you assumed queries were cheap.
- What happens to the ordering if you transfer only half of the inbound stack?Order still survives, provided the outbound stack was empty when you started and you never transfer again until it drains. The transferred prefix is a correct in-order block. Moving everything is simply the standard choice: it keeps the code and the cost argument simple, since each element then crosses exactly once.
A single narrow chute pours items out backwards, so you pour them through a second chute to flip them upright. But you only pour when the second chute has emptied — otherwise the new batch lands on top of the old and gets handed out first.
saying these in an interview costs you the question
- Transfers elements back and forth on every operation
- Claims order survives pushing onto a non-empty outbound stack
- Reports the queue empty by checking only one stack
- Describes the transfer as sorting the pending elements
- Assumes peek never touches internal state