vault

Queue from Two Stacks

17 min read

Queue from Two Stacks

Build a Queue (FIFO, First-In-First-Out) using only two Stacks (LIFO, Last-In-First-Out). Unlike its symmetric twin Stack from Two Queues — which is Θ(n) per operation in the worst case no matter what — this construction admits a beautiful O(1) amortized solution: every queue op runs in O(1) on average across any sequence of operations, even though some individual ops cost Θ(n). The construction is one of the cleanest worked examples of Amortized Analysis in the curriculum and appears in CLRS Chapter 17 (problem 17-2 in older editions, exercise 17.1-3 in the third edition) as a paradigmatic illustration of the aggregate, accounting, and potential methods. It is also closely related to the banker’s queue in functional programming (Chris Okasaki, Purely Functional Data Structures, 1998, §5.2). The interview problem is LeetCode 232 (Implement Queue using Stacks).

1. Intuition — The Two-Tray Cafeteria Belt

Imagine a cafeteria with a single conveyor belt that needs to serve customers FIFO (first arrived, first served), but you only have two stacks of trays to work with. Newcomers add their tray to one stack — the in-stack, where the latest arrival is always on top. When a customer is served, you can’t easily reach the bottom of that stack (where the oldest tray is) — that’s the wrong end. So you set up a second stack — the out-stack — that holds trays already turned upside-down relative to arrival order: the bottom of in-stack now sits at the top of out-stack.

The trick is to transfer trays from in-stack to out-stack only when the out-stack is empty and only when a customer asks to be served. When a tray is popped from the in-stack and pushed onto the out-stack, it physically inverts: a tray that was near the bottom of the in-stack ends up near the top of the out-stack. After draining the entire in-stack, the out-stack is the in-stack reversed — and reading it top-to-bottom is reading the original arrival order, oldest first. That’s exactly FIFO.

The crucial design decision: lazy transfer. We don’t move anything until forced to (i.e., until a dequeue finds the out-stack empty). And once we do move, we move everything at once. This batches the cost of inversion so each element pays for its own move exactly twice over its lifetime — once into the in-stack, once from in-stack to out-stack — and that’s it. Subsequent dequeues hit the already-prepared out-stack at O(1).

The amortized argument generalizes the cafeteria intuition: across any sequence of n operations, the total work is O(n), not because each operation is cheap, but because each element passes through each stack at most twice. The expensive transfers, when they happen, are paid for by the enqueue operations that put those elements there. This is the accounting method of amortized analysis in microcosm.

2. Tiny Worked Example

We trace enqueue 1, enqueue 2, dequeue, enqueue 3, dequeue, dequeue, enqueue 4, dequeue. The convention: in-stack [bottom ... top], out-stack [bottom ... top]. The “front” of the queue is the top of the out-stack; if out-stack is empty, the front is the bottom of the in-stack (and a transfer is needed before serving).

StepOpin-stackout-stackReturns
0start[][]—
1enqueue 1[1][]—
2enqueue 2[1, 2][]—
3adequeue: out empty → transfer[][2, 1](pre-transfer state)
3bdequeue: pop top of out[][2]1
4enqueue 3[3][2]—
5dequeue: out non-empty → pop[3][]2
6adequeue: out empty → transfer[][3](transfer)
6bdequeue: pop top[][]3
7enqueue 4[4][]—
8adequeue: out empty → transfer[][4](transfer)
8bdequeue: pop top[][]4

The interesting steps are 3 and 6: a dequeue arrived with an empty out-stack, so the algorithm bulk-transferred the in-stack onto the out-stack (reversing the order) before serving. After step 3a, the out-stack reads [2, 1] — top is 1, which is correct because 1 was enqueued first. Step 5 is also instructive: the out-stack already had [2] from the previous transfer, so the dequeue went straight to it without disturbing the in-stack [3]. This is exactly the lazy-batching strategy: we never re-transfer; once an element is on the out-stack, it stays there until popped.

A common bug surfaces if you transfer eagerly (i.e., on every enqueue, “rebalance” the stacks): you end up paying the transfer cost on every enqueue, ballooning to O(n) per op. Lazy is necessary.

3. Pseudocode

class QueueUsingStacks:
    in_stack:  Stack       # holds recently-enqueued items, top = newest
    out_stack: Stack       # holds older items reversed, top = oldest still in queue

    enqueue(x):
        in_stack.push(x)                       # always cheap

    dequeue():
        if out_stack.is_empty():
            transfer()                         # bulk move
        if out_stack.is_empty():               # both empty → queue is empty
            error "dequeue from empty queue"
        return out_stack.pop()

    peek():                                    # the front of the queue
        if out_stack.is_empty():
            transfer()
        if out_stack.is_empty():
            error "peek on empty queue"
        return out_stack.top()

    is_empty():
        return in_stack.is_empty() and out_stack.is_empty()

    size():
        return in_stack.size() + out_stack.size()

    transfer():                                # PRIVATE — only called when out_stack is empty
        while not in_stack.is_empty():
            out_stack.push( in_stack.pop() )

The single-line transfer routine is the heart of the construction. The precondition that out-stack is empty before transfer is essential: if the out-stack already held some elements, transferring would interleave them with the older in-stack contents in the wrong order (the freshly-transferred elements, themselves reversed, would sit on top of the genuinely-older elements, which would now be served after the newer ones — wrong).

4. Python Implementation

class QueueUsingStacks:
    """FIFO queue on top of two LIFO stacks. All ops are O(1) amortized.
 
    The two stacks play complementary roles:
      - `_in_stack`  — accepts new arrivals.        Top = newest pushed.
      - `_out_stack` — serves them out.            Top = next to be dequeued (oldest).
 
    Invariant: `_out_stack`, viewed from top to bottom, holds the oldest
    elements in queue order. When it's empty, the next dequeue triggers a
    bulk transfer of `_in_stack`'s contents into `_out_stack`, reversing
    them — which is exactly the operation that turns LIFO into FIFO.
    """
 
    def __init__(self) -> None:
        self._in_stack: list[int] = []
        self._out_stack: list[int] = []
 
    def push(self, x: int) -> None:                # LC API uses `push` for enqueue
        self._in_stack.append(x)                    # O(1)
 
    def pop(self) -> int:                           # LC API uses `pop` for dequeue
        self._move_if_needed()
        if not self._out_stack:
            raise IndexError("pop from empty queue")
        return self._out_stack.pop()                # amortized O(1) — see §5
 
    def peek(self) -> int:
        self._move_if_needed()
        if not self._out_stack:
            raise IndexError("peek on empty queue")
        return self._out_stack[-1]
 
    def empty(self) -> bool:                        # noqa: A003
        return not self._in_stack and not self._out_stack
 
    def _move_if_needed(self) -> None:
        """Transfer all of in_stack onto out_stack only when out_stack is empty.
 
        The 'only when empty' precondition is essential — see Pitfall 8.3."""
        if self._out_stack:
            return
        while self._in_stack:
            self._out_stack.append(self._in_stack.pop())

A short sanity test:

def _demo() -> None:
    q = QueueUsingStacks()
    q.push(1)
    q.push(2)
    assert q.peek() == 1
    assert q.pop() == 1
    q.push(3)
    assert q.pop() == 2
    assert q.pop() == 3
    q.push(4)
    assert q.pop() == 4
    assert q.empty()
 
if __name__ == "__main__":
    _demo()

The implementation is short — perhaps 15 lines of substantive code. The cleverness is entirely in the two-stack invariant and the lazy-transfer policy; once those are right, the code follows mechanically.

5. Amortized Complexity Analysis

This is the section that turns the problem from a curiosity into a model of Amortized Analysis. We give two complementary arguments — the aggregate method and the accounting method — both reaching the same conclusion: each operation is O(1) amortized.

5.1 Aggregate Method

Claim. The total cost of any sequence of n operations on the two-stack queue is O(n).

Argument. Consider the lifetime of a single element x:

  • When enqueue(x) is called, x is pushed onto in_stack. Cost: 1 stack-push operation.
  • At some later moment (possibly), x is moved during a transfer: popped from in_stack, pushed onto out_stack. Cost: 2 stack operations.
  • At a still later moment (possibly), x is popped from out_stack and returned by a dequeue. Cost: 1 stack-pop operation.

Total stack operations for x over its lifetime: at most 4 (one push to in, one pop from in, one push to out, one pop from out). Some elements never get transferred or never get dequeued — those cost less. Critically, no element is ever transferred twice: once it’s on out_stack, it stays there until popped, and by then out_stack has been drained (since pops only happen on out_stack).

For n queue operations, the total number of underlying stack operations is at most 4n. Since each underlying stack operation is O(1) (using a Stack backed by a dynamic array — see Stack for the amortized-O(1) push argument), the total work is O(n). Dividing by n gives O(1) amortized per queue operation. ∎

5.2 Accounting Method

The accounting method assigns “credits” to each cheap operation, deferring them to pay for the occasional expensive one.

Charging scheme. Charge each enqueue 3 units of work: 1 unit pays for the actual in_stack.push, and 2 units are deposited as credit on the element. Charge each dequeue 1 unit of work: it pays for the out_stack.pop.

Why this covers all real costs:

  • An enqueue(x) pays 1 unit immediately for in_stack.push(x) and saves 2 units of credit “stuck to” element x.
  • When x is later transferred (during a dequeue that found out_stack empty), it costs 2 actual stack operations: in_stack.pop and out_stack.push. Both are paid by the 2 saved units of credit on x. The transfer is prepaid.
  • When x is finally returned by a dequeue, that dequeue pays its own 1 unit for out_stack.pop.

Every actual stack operation is paid for, by either an enqueue’s deferred credit or a dequeue’s direct charge. Since each queue op is charged at most 3 units, the amortized cost is O(1) per queue operation. ∎

The accounting method makes vivid what the aggregate method asserts only in totals: the enqueue effectively prepays the cost of moving its element to the out-stack. The system is “solvent” at all times — the total credit outstanding never goes negative, because every element on the in-stack still carries its 2 units, ready to fund the eventual transfer.

5.3 Worst-Case Per Operation

Individual operations are not O(1). Specifically:

  • enqueue is always O(1) worst-case.
  • dequeue is O(1) when out_stack is non-empty, but Θ(n) worst-case when it’s empty and the in-stack holds n elements that all need transferring.

A real-time variant of this construction exists — Okasaki’s real-time queue (Purely Functional Data Structures, 1998, §7.2) — which achieves O(1) worst-case per operation by interleaving the transfer one element per dequeue rather than batching it. The price is more complex code and lazy evaluation; in imperative interview settings, the amortized-O(1) version is the expected answer.

5.4 Space

O(n) — every enqueued-and-not-yet-dequeued element lives in exactly one of the two stacks (never both at once, because transfer empties the in-stack). The total space across both stacks equals the queue’s logical size.

6. Variants and Connections

6.1 Banker’s Queue (Functional / Purely Functional)

In purely functional languages where stacks are persistent linked lists (cons-lists), the same two-list construction is called the banker’s queue (Okasaki §6.3.2 — or a variant of it). It uses two cons-lists: a front list (analogous to out-stack) and a rear list (analogous to in-stack reversed). When the front list becomes empty, the rear list is reversed and becomes the new front list. The same amortized O(1) analysis applies. This is one of the standard purely-functional queue constructions.

6.2 Real-Time Queue

To eliminate the Θ(n) worst-case dequeue, Okasaki §7.2 spreads the reversal lazily across multiple operations: each operation forces one suspended thunk of work, so the reversal completes incrementally as new operations come in. The resulting queue has O(1) worst-case per operation, not just amortized — at the cost of more involved bookkeeping and reliance on lazy evaluation. The technique generalizes to many other persistent data structures.

6.3 Steque (Stack-Ended Queue) and Deques from Stacks

A steque (Sedgewick & Wayne, Algorithms 4th ed.) is a stack-with-an-additional-enqueue-at-the-rear; building it from two stacks is similar but admits push-front, push-back, and pop-front in O(1) amortized. A full Deque (with both pop-front and pop-back) requires more machinery — the standard construction uses three stacks or a single deque primitive.

6.4 Min/Max Queue from Min/Max Stacks

Combine the two-stack queue construction with the Min Stack technique on each underlying stack to produce a queue with O(1) amortized getMin(). The min of the whole queue is the min of the two stacks’ mins. Each underlying stack tracks its own running min via the lockstep auxiliary technique. This is an excellent advanced interview problem (“design a queue that supports min in constant amortized time”).

6.5 Concurrent Variants

In a multi-producer/multi-consumer setting, the two-stack queue’s transfer step is a coarse-grained critical section that all consumers must serialize on. Lock-free queues (Michael & Scott 1996 PODC paper) use a different approach — linked nodes with CAS — but the two-stack idea inspires some hybrid lock-based constructions where the transfer is the only point of contention.

7. Use Cases and Why It Matters

In production code, you’d just use a real queue (collections.deque in Python, ArrayDeque in Java, std::queue in C++) — none of which are built on this two-stack trick internally. So why is this construction important?

  1. Pedagogical purity. It is the cleanest non-trivial illustration of amortized analysis. The accounting method’s “deferred work” intuition lands naturally; students who grasp this go on to understand dynamic-array growth, splay trees, and Fibonacci heaps more easily.
  2. Functional-programming foundations. As noted, the same idea underlies Okasaki’s banker’s queue, which is the standard purely-functional FIFO queue. Persistent data structures used in immutable contexts (e.g., Clojure, Haskell’s Data.Sequence precursors) rely on these constructions.
  3. Interview signaling. The problem reliably distinguishes candidates who memorize “two stacks, one for in, one for out” from those who can articulate why the amortization works — and especially why the lazy-transfer policy is necessary and the eager-transfer alternative fails.
  4. Building block for other ADTs. As shown in §6.4, the construction composes with augmentations (min, max, sum) to produce more sophisticated queue variants without changing the asymptotic behavior.

8. Pitfalls

  1. Eager transfer (transferring on every enqueue). This is the most common bug. If you “rebalance” the stacks on every enqueue to “keep them ready,” every enqueue becomes O(n) and the amortization is destroyed. The whole point is lazy transfer: only when an empty out_stack forces the move.
  2. Transferring while out_stack is non-empty. This breaks FIFO: the freshly-transferred (and reversed) elements sit on top of older elements that arrived earlier, meaning the next pop returns a later-arrived element. The transfer’s precondition out_stack.is_empty() is non-negotiable.
  3. Forgetting to handle empty queue in dequeue/peek. After calling transfer, out_stack may still be empty (if in_stack was also empty). Always re-check before popping. A common bug is to assume “we just transferred, so out_stack is non-empty.”
  4. Confusing this construction with Stack from Two Queues. Both involve two of one ADT emulating the other, but only this one (queue from stacks) admits amortized O(1). The other is Θ(n) per op no matter what. Mixing them up is a common interview slip.
  5. Misstating the worst-case as O(1). Worst-case per operation is Θ(n) on the unlucky dequeue that triggers a transfer of n elements. The interviewer wants you to distinguish amortized from worst-case — saying “O(1) amortized, with O(n) worst-case dequeue” is the correct phrasing.
  6. Not recognizing the connection to the banker’s queue. In a stronger interview, mentioning “this is essentially Okasaki’s banker’s queue” demonstrates broader understanding. It’s not required but it’s a credible signal.
  7. Stack overflow on a large transfer. If transfer is implemented recursively (each recursive call pops one element), it overflows the call stack on a large in-stack. Always use an explicit while-loop (as in the pseudocode and Python). This is the same lesson as in Tree Traversals.
  8. Thread safety. Two threads sharing this queue can race during transfer: a concurrent enqueue mid-transfer can put an element on the in-stack that should have moved over with the others, breaking ordering. Use a lock around the entire enqueue/dequeue operations or use a true concurrent queue.
  9. Double-popping in dequeue. A subtle bug: after transfer, if you accidentally also pop from in_stack in the same operation (perhaps because of a copy-paste error in the pop sequence), you’ve effectively skipped an element. Keep the responsibilities separate: transfer only moves elements; the actual dequeue happens only via out_stack.pop().

9. Diagram — Lifetime of an Element

sequenceDiagram
    participant U as caller
    participant I as in_stack
    participant O as out_stack
    U->>I: enqueue 1 → push 1
    Note right of I: in=[1], out=[]
    U->>I: enqueue 2 → push 2
    Note right of I: in=[1,2], out=[]
    U->>O: dequeue: out empty → transfer
    Note over I,O: pop 2 from in → push 2 to out
    Note over I,O: pop 1 from in → push 1 to out
    Note right of O: in=[], out=[2,1]
    U->>O: dequeue → pop top of out
    Note right of O: returns 1; in=[], out=[2]
    U->>I: enqueue 3 → push 3
    Note right of I: in=[3], out=[2]
    U->>O: dequeue → pop top of out
    Note right of O: returns 2; in=[3], out=[]
    U->>O: dequeue: out empty → transfer
    Note over I,O: pop 3 from in → push 3 to out
    U->>O: dequeue → pop top of out
    Note right of O: returns 3

What this diagram shows. A swimlane sequence diagram tracking elements 1, 2, 3 through the queue. Three observations:

  1. Each element passes through in_stack exactly once (on enqueue), and at most once through out_stack (on transfer). After being on out_stack, it is popped and gone — never re-transferred. This is the constant-factor bound (4 stack ops per element) that drives the amortized analysis.
  2. The transfers happen only when the out-stack is empty and a dequeue requests service — never proactively. This is the lazy-transfer policy.
  3. After step 5 (the second dequeue), in_stack holds [3] and out_stack is empty. The next dequeue (step 6) triggers another transfer — moving the lone 3 over — even though the in-stack only had one element. The cost is small here, but the algorithm doesn’t optimize this case specially: it uses the same uniform recipe regardless of the in-stack’s size.

The diagram also exposes the non-uniform cost of dequeues: some return immediately (steps 4 and 7 in the diagram are O(1)), others trigger a transfer (the second dequeue’s transfer line spans two stack operations). The amortized analysis sums these to O(1) per op when divided across all operations.

10. Common Interview Problems

#ProblemConnection
LC 232Implement Queue using StacksThe canonical problem — write the two-stack solution and articulate the amortized argument
LC 225Implement Stack using QueuesThe dual, asymmetric problem — see Stack from Two Queues
LC 622Design Circular QueueDifferent ADT-design drill
LC 933Number of Recent CallsA queue used in production-style code; can be implemented with two stacks for fun
LC 346Moving Average from Data StreamUses a queue-shaped sliding window
LC 155Min StackAugmenting a stack — combine with this to make a min queue (see §6.4)

11. Open Questions

  • Can the worst-case Θ(n) dequeue be eliminated without lazy evaluation in an imperative-only setting? Okasaki’s real-time queue uses lazy evaluation; a fully eager variant requires either deque primitives or a different algorithm. I haven’t found a clean construction that uses only stack primitives and achieves O(1) worst-case eagerly — possibly because none exists.
  • How does the two-stack queue compare empirically to collections.deque in Python for typical workloads? deque is implemented as a doubly-linked list of fixed-size blocks (CPython source: Modules/_collectionsmodule.c). The two-stack queue should be slightly worse on cache locality due to the bursty transfer, but the amortized cost matches.
  • What’s the right way to extend the construction to a deque (push and pop at both ends) using only stack primitives? The standard answer involves three stacks or rebalancing tricks; I haven’t seen a clean two-stack deque.

12. See Also

Graph View

Backlinks