vault

Stack from Two Queues

17 min read

Stack from Two Queues

An exercise in abstract-data-type emulation: build a Stack (LIFO, Last-In-First-Out) using only two Queues (FIFO, First-In-First-Out) and their five primitive operations — enqueue, dequeue, front, is_empty, size. The challenge is that every queue primitive contradicts the stack’s access pattern: the most recently enqueued element is the last one to come out of a queue, while a stack must yield it first. The classic solutions push the cost of the inversion entirely into either push or pop. Two clean strategies emerge, dual to each other in their cost distribution; a third single-queue trick achieves the same effect with one container. The problem is LeetCode 225 (Implement Stack using Queues) and is the symmetric twin of Queue from Two Stacks (LeetCode 232) — together they illustrate that conversion between two LIFO/FIFO orderings is always asymmetric in cost.

1. Intuition — Reversing the Conveyor Belt

Picture a sushi conveyor belt as a queue: plates ride from left to right; the chef adds new plates on the left, customers take plates from the right. The dish that the chef placed first is the dish the customer eats first — strict FIFO. Now suppose a customer demands a stack experience: they want the most recently placed plate first. With only this conveyor belt, you cannot satisfy them — the freshest plate is always at the left, hidden behind every older plate.

So you bring in a second conveyor belt. When a new plate arrives, you have a choice: spend extra effort now to put the new plate at the right end of the second belt (where it will be “next out”), or spend extra effort later when the customer asks for it. Both belts run FIFO; the trick is to use one as scratch space to flip the order on demand. The two clean strategies are these:

  • Push-heavy strategy. When a new plate arrives, route every existing plate from belt 1 across to belt 2, then place the new plate on belt 1 (now the only plate there), then route everything back. Net effect: the newest plate is at the front of belt 1 and ready to be removed in O(1). But every push costs a full pass over the structure.
  • Pop-heavy strategy. Just enqueue new plates onto belt 1 normally — push is O(1). When a customer asks for a plate, transfer all but the last plate from belt 1 to belt 2, give the last plate to the customer, then swap belt names so belt 2 (which has all the older plates in original order) becomes the new belt 1.

Both strategies pay the inversion cost once per element somewhere in its lifetime. Which to choose depends on the workload: if pushes vastly outnumber pops, the pop-heavy strategy wins; if pops vastly outnumber pushes, the push-heavy strategy wins. (In a balanced workload, they are equivalent.)

The deeper lesson: any time you emulate a data structure on top of one that has the opposite ordering discipline, the conversion cost is fundamental and cannot be eliminated — only relocated.

2. Tiny Worked Example — Push-Heavy Strategy

We use the convention q1.front -> q1.rear. The customer-visible operations: push(1), push(2), push(3), pop, pop, push(4), pop.

StepOpActionq1q2Returns
0start—[][]—
1push 1q1 empty → enqueue 1 directly[1][]—
2push 2move all from q1 to q2; enqueue 2 to q1; move q2 back to q1[2, 1][]—
3push 3same recipe with q1=[2,1][3, 2, 1][]—
4popdequeue front of q1[2, 1][]3
5popdequeue front of q1[1][]2
6push 4recipe — q2 holds [1] briefly, q1 = [4], move q2 back[4, 1][]—
7popdequeue front of q1[1][]4

Notice the order on q1: the rear of q1 always contains the oldest element pushed (and so closest to the bottom of the stack), and the front of q1 always contains the newest (top of the stack). Pop is then a single q1.dequeue(). The price is paid up front in push.

A diagram of step 2 in detail:

push(2):
  q1 = [1], q2 = []

  Phase A — drain q1 to q2:
    while not q1.is_empty(): q2.enqueue(q1.dequeue())
    q1 = [], q2 = [1]

  Phase B — put new element alone in q1:
    q1.enqueue(2)
    q1 = [2], q2 = [1]

  Phase C — drain q2 back into q1 (now after the 2):
    while not q2.is_empty(): q1.enqueue(q2.dequeue())
    q1 = [2, 1], q2 = []

After phase C, q1.front == 2, q1.rear == 1 — newest at front, ready for O(1) pop.

3. Pseudocode

3.1 Strategy A — Push O(n), Pop O(1)

class StackUsingQueues:
    q1: Queue
    q2: Queue           # always empty between operations

    push(x):
        # Drain q1 into q2 so q1 is empty.
        while not q1.is_empty():
            q2.enqueue( q1.dequeue() )
        # Place new element as the sole occupant of q1.
        q1.enqueue(x)
        # Drain q2 back into q1, after x.
        while not q2.is_empty():
            q1.enqueue( q2.dequeue() )

    pop():
        return q1.dequeue()                    # O(1)

    top():
        return q1.front()                      # O(1)

    is_empty():
        return q1.is_empty()

A simpler-to-write variant: enqueue to q2 first, then drain q1 into q2, then swap the names q1↔q2. Functionally identical; the “swap names” trick avoids the second drain pass:

push_v2(x):
    q2.enqueue(x)
    while not q1.is_empty():
        q2.enqueue( q1.dequeue() )
    swap(q1, q2)                # now q1 holds [x, oldest..., newest_before_x]; q2 empty

3.2 Strategy B — Push O(1), Pop O(n)

class StackUsingQueues:
    q1: Queue           # holds elements in arrival order
    q2: Queue           # scratch

    push(x):
        q1.enqueue(x)                          # O(1)

    pop():
        # Move all but the last from q1 to q2.
        while q1.size() > 1:
            q2.enqueue( q1.dequeue() )
        result := q1.dequeue()                 # this is the last-pushed element
        swap(q1, q2)                           # q2 (now holding the older order) becomes q1
        return result

    top():
        # Same as pop, but re-enqueue the last element.
        while q1.size() > 1:
            q2.enqueue( q1.dequeue() )
        result := q1.dequeue()
        q2.enqueue(result)                     # put it back so the stack is unchanged
        swap(q1, q2)
        return result

    is_empty():
        return q1.is_empty()

3.3 Single-Queue Trick — Push O(n), Pop O(1)

A small twist: a single queue is enough if you use rotation to bring the newest element to the front:

class StackUsingOneQueue:
    q: Queue

    push(x):
        n := q.size()
        q.enqueue(x)                           # x goes to the back
        for _ in range(n):                     # rotate n times: each old element moves to back
            q.enqueue( q.dequeue() )
        # After the loop, x is at the front.

    pop():
        return q.dequeue()                     # O(1)

    top():
        return q.front()                       # O(1)

The rotation does the work of the second queue: it loops the older elements all the way around, so the new element ends up at the front. This implementation is the most concise — and almost certainly what the LC 225 problem author had in mind, because the “follow up: implement using only one queue” hint appears in the original prompt.

4. Python Implementation

We pick collections.deque as the underlying queue: it gives true O(1) append (rear enqueue) and popleft (front dequeue), unlike list whose pop(0) is O(n) (Python docs: collections.deque).

4.1 Strategy A — Push O(n), Pop O(1) (with the swap-names variant)

from collections import deque
 
class StackUsingQueuesPushHeavy:
    """LIFO stack on top of two FIFO queues. push is O(n), pop is O(1).
 
    Invariant maintained between operations: q1 holds all elements with the
    most-recently-pushed at the FRONT (q1[0]) and the oldest at the REAR.
    q2 is empty between operations and is used only as scratch in push().
    """
 
    def __init__(self) -> None:
        self.q1: deque[int] = deque()
        self.q2: deque[int] = deque()
 
    def push(self, x: int) -> None:
        # Place new element first into the empty q2 so it ends up at q2's front.
        self.q2.append(x)
        # Drain q1 onto q2 — older elements now sit AFTER x in q2.
        while self.q1:
            self.q2.append(self.q1.popleft())
        # Swap names: the queue that holds the desired order becomes q1.
        # In Python this is a cheap reference swap, not a copy.
        self.q1, self.q2 = self.q2, self.q1
 
    def pop(self) -> int:
        if not self.q1:
            raise IndexError("pop from empty stack")
        return self.q1.popleft()
 
    def top(self) -> int:
        if not self.q1:
            raise IndexError("top on empty stack")
        return self.q1[0]
 
    def empty(self) -> bool:                    # noqa: A003 (LC API uses `empty`)
        return not self.q1

4.2 Strategy B — Push O(1), Pop O(n)

from collections import deque
 
class StackUsingQueuesPopHeavy:
    """LIFO stack on top of two FIFO queues. push is O(1), pop is O(n)."""
 
    def __init__(self) -> None:
        self.q1: deque[int] = deque()
        self.q2: deque[int] = deque()
 
    def push(self, x: int) -> None:
        self.q1.append(x)
 
    def pop(self) -> int:
        if not self.q1:
            raise IndexError("pop from empty stack")
        # Move all but the most recently pushed (which is at the rear) into q2.
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        result = self.q1.popleft()              # this is the rear == most recent
        self.q1, self.q2 = self.q2, self.q1     # the older elements regain "primary" status
        return result
 
    def top(self) -> int:
        if not self.q1:
            raise IndexError("top on empty stack")
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        result = self.q1.popleft()
        self.q2.append(result)                  # put it back: top is non-destructive
        self.q1, self.q2 = self.q2, self.q1
        return result
 
    def empty(self) -> bool:
        return not self.q1

4.3 Single-Queue Implementation

from collections import deque
 
class StackUsingOneQueue:
    """LIFO stack on top of ONE FIFO queue, using rotation. push is O(n), pop is O(1)."""
 
    def __init__(self) -> None:
        self.q: deque[int] = deque()
 
    def push(self, x: int) -> None:
        self.q.append(x)
        # Rotate: dequeue every previously-existing element and re-enqueue it.
        # After (n-1) rotations the newly-pushed x lands at the front.
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
 
    def pop(self) -> int:
        if not self.q:
            raise IndexError("pop from empty stack")
        return self.q.popleft()
 
    def top(self) -> int:
        if not self.q:
            raise IndexError("top on empty stack")
        return self.q[0]
 
    def empty(self) -> bool:
        return not self.q

The single-queue version is what most interviewers expect when they ask “and now do it with only one queue.” Note that on collections.deque, deque.rotate(-1) could replace the dequeue/enqueue pair, but rotate moves all elements at once and you’d need to think about direction; the explicit loop is clearer.

4.4 Sanity Test

def _demo() -> None:
    for cls in (StackUsingQueuesPushHeavy, StackUsingQueuesPopHeavy, StackUsingOneQueue):
        s = cls()
        for x in [1, 2, 3]:
            s.push(x)
        assert s.top() == 3
        assert s.pop() == 3
        assert s.pop() == 2
        s.push(4)
        assert s.pop() == 4
        assert s.pop() == 1
        assert s.empty()
 
if __name__ == "__main__":
    _demo()

5. Complexity

StrategypushpoptopTotal over n ops
A: push-heavy (two queues)O(n)O(1)O(1)O(n²) worst-case
B: pop-heavy (two queues)O(1)O(n)O(n)O(n²) worst-case
C: single queue with rotationO(n)O(1)O(1)O(n²) worst-case

Why both strategies are O(n²) over n mixed operations. Suppose all operations are pushes (Strategy A). The k-th push touches every of the previous k−1 elements, so the cumulative work is 0 + 1 + 2 + ... + (n−1) = n(n−1)/2 = O(n²). The dual holds for Strategy B with all pops after a batch of pushes: the j-th pop scans (n−j) elements, summing to O(n²) as well.

No constant-amortized solution exists with two queues. Unlike Queue from Two Stacks — where each element passes through each underlying stack at most twice for an amortized O(1) per op — there is no analogous trick using two queues. The reason is structural: in a queue, the “old” end and the “new” end are at opposite physical positions, and every transfer operation moves elements one-by-one in their original order; you can never reverse a sub-sequence cheaply. With stacks, transferring all elements of one stack onto another does reverse them (because pushing to a stack hits the top while popping from another stack reads its top), and that single reversal is what the queue-from-stacks construction exploits. The asymmetry is fundamental.

Verify: lower bound formality

The claim “no O(1) amortized stack-from-two-queues exists” is widely believed and matches the cost of all known constructions, but I don’t have a rigorous lower-bound proof to point to. Folk explanation: each enqueue can only place an element at the rear, each dequeue can only read the front, so to bring a particular non-end element into reach requires Ω(distance) operations and there is no way to amortize because the distances grow with n.

Space. O(n) regardless of strategy — exactly as many elements live in the underlying queues as have been pushed (minus those popped). The two-queue version uses one of the two queues as scratch and never holds more than n elements total across both.

6. Comparison and Trade-Off Discussion

Choosing between Strategy A and Strategy B is a question of which operation is on the critical path in the calling workload:

  • If pushes dominate (e.g., the stack accumulates state for a brief moment then is fully drained), Strategy B (push O(1), pop O(n)) is clearly better.
  • If pops dominate (e.g., a stack pre-loaded once then queried many times — unlikely in practice but possible), Strategy A wins.
  • If both are comparable, the costs are equivalent and the simpler implementation should win — typically the single-queue version, because it has half the bookkeeping and exactly one container to reason about.

In practice, nobody uses this in production — you would just use a real stack. The exercise exists because it tests:

  1. Whether the candidate understands LIFO vs FIFO are not interchangeable surface-level interfaces but represent a genuine ordering invariant.
  2. Whether the candidate can identify where the inversion cost has to live and articulate the trade-off rather than hand-waving.
  3. Whether the candidate notices the single-queue simplification.

The companion problem Queue from Two Stacks flips the question — and crucially, that one admits an amortized O(1) solution. The asymmetry is the most interesting takeaway from doing both problems.

7. Variants and Generalizations

7.1 Stack from k Queues

If you’re given more than two queues, can the cost improve? Surprisingly, no. The fundamental obstacle is that queues only allow single-ended access; adding more queues just gives you more scratch space, which doesn’t change the asymptotic cost of the inversion. The best known is still O(n) per stack op (push or pop, your choice).

7.2 Deque from Two Queues

Building a Deque (double-ended queue) on top of two queues is a related exercise. Push-front and push-back can each be made O(1) by enqueuing onto the appropriate queue; pop-front is O(1) via a dequeue, but pop-back is O(n) via the same scan-all-but-last trick. The deque case is asymmetric — front-side ops are cheap, back-side pops are expensive.

7.3 Persistent Stack from Queues

In a functional/persistent setting, queues don’t have a cheap back end either, so the construction inherits all the asymptotic problems. Real persistent stacks are built directly as cons-lists; the queue-emulation construction is purely an interview curiosity.

8. Pitfalls

  1. Forgetting to swap queue names after push (Strategy A) or pop (Strategy B). Both strategies rely on the names q1 and q2 always referring to the queue that currently holds the data in the canonical order. If you forget the swap, the next operation reads from the wrong queue and silently produces wrong answers.
  2. Using list.pop(0) as a queue. Python’s list.pop(0) is O(n) because it shifts every element down. Using a list to back the queue turns even Strategy B’s O(1) push into O(n) and Strategy A’s O(n) push into O(n²) per call. Always use collections.deque.
  3. Confusing push-heavy with pop-heavy. Both strategies use two queues but their cost distributions differ. Read the problem statement (or the interviewer’s preference) carefully before committing — LeetCode 225 accepts either, but some interviewers will insist on a specific one to test that you understand both.
  4. Calling top() cheap in Strategy B. top in Strategy B has the same cost as pop because you must scan to the rear of the queue to find the most-recent element (and then put it back). Naïve candidates assume top is always O(1) and miss that it inherits pop’s cost in this strategy.
  5. Single-queue version with the wrong rotation count. The rotation must be exactly len(q) - 1 times after the push (i.e., move every element previously in the queue past the newly added one). Off-by-one gives a different element at the front than the most-recently-pushed.
  6. Empty-queue dequeue. Calling popleft on an empty deque raises IndexError. Guard pop and top with empty checks if the spec doesn’t promise the caller checks first.
  7. Thread safety. collections.deque is not thread-safe for the kinds of compound operations done here (drain-and-refill). If multiple threads use this stack, wrap with a lock or use queue.Queue (which is thread-safe but slower).
  8. Producing a “stable” stack when ties matter. Stack discipline doesn’t actually have ties — every element has a unique LIFO position by arrival order. This pitfall is mostly a non-issue, but be aware that if you augment the stack with priorities or other equivalence, the underlying queue-based emulation doesn’t preserve any “tie-breaking by insertion order” semantics for free.

9. Diagram — Strategy A in Action

flowchart TD
    subgraph T0["Before push(3)"]
        A1["q1: front [2, 1] rear"]
        A2["q2: empty"]
    end
    subgraph T1["push(3) phase A — drain q1 to q2"]
        B1["q1: empty"]
        B2["q2: front [2, 1] rear"]
    end
    subgraph T2["push(3) phase B — enqueue 3 alone in q1"]
        C1["q1: [3]"]
        C2["q2: front [2, 1] rear"]
    end
    subgraph T3["push(3) phase C — drain q2 back into q1"]
        D1["q1: front [3, 2, 1] rear"]
        D2["q2: empty"]
    end
    T0 --> T1 --> T2 --> T3

What this diagram shows. Four labeled snapshots of the state of q1 and q2 as Strategy A executes a single push(3) against an existing stack containing [2, 1] (with 2 on top). The four-phase choreography is: (T0) initial state with the older elements [2, 1] in q1, oldest at rear; (T1) drain everything from q1 into q2, preserving order — q2 now holds [2, 1]; (T2) enqueue the new element 3 into the now-empty q1, alone; (T3) drain q2 back into q1 behind the 3 — q1 now holds [3, 2, 1] with the newest at the front. After this, a pop() is just q1.popleft() returning 3 in O(1). The total cost of the push is proportional to the number of elements moved — O(n).

The diagram makes the asymmetry visible: 3 is the only “new” piece of information, but every existing element had to be shuffled across and back to give 3 the position it deserves at the front of the FIFO.

10. Common Interview Problems

#ProblemConnection
LC 225Implement Stack using QueuesThe canonical problem — write all three variants
LC 232Implement Queue using StacksThe dual — and famously does admit amortized O(1); see Queue from Two Stacks
LC 622Design Circular QueueDifferent ADT-emulation drill
LC 641Design Circular DequeBuilds a Deque from arrays — same family
LC 155Min StackAugment a stack — see Min Stack; same “stack ADT design” theme

11. Open Questions

  • Is there a formal lower-bound proof that any stack implementation using only two queue primitives must have either Ω(n) push or Ω(n) pop in the worst case? Folklore says yes; I haven’t located a clean proof. The closest analogue is the lower bound for sorting on a queue model of computation.
  • Do persistent / functional queues (banker’s queues, real-time queues with O(1) worst-case via lazy evaluation, e.g., Okasaki’s Purely Functional Data Structures, Ch. 4–5) help here? Probably not — the cost lives in the data flow, not the underlying queue’s amortization.
  • In a multi-producer / multi-consumer setting, is the pop-heavy strategy (push O(1)) more lock-friendly than the push-heavy strategy? Push contention is naturally lower because each push is a single enqueue; pop contention is fierce because pop drains the whole queue, holding the lock for the entire scan.

12. See Also

  • Stack — the data structure being emulated; explains LIFO discipline and standard implementations
  • Queue — the data structure used as the primitive; explains FIFO discipline
  • Deque — generalizes both; if you have a deque, you can implement either side natively in O(1)
  • Queue from Two Stacks — the dual problem, with a much better amortized cost
  • Min Stack — sibling “augment / emulate a stack” problem; same data-structure design theme
  • Amortized Analysis — framework for understanding why the queue-from-stacks dual works and this one doesn’t (planned)
  • Big-O Notation
  • SWE Interview Preparation MOC

Graph View

Backlinks