juniorStacks

How do you implement a queue using two stacks?

Updated Feb 20, 2026

Short answer

Keep two stacks — an inbox for pushes and an outbox for pops. Enqueue always pushes onto the inbox. Dequeue pops from the outbox, and when the outbox is empty, first pour the entire inbox into it, which reverses the order and turns LIFO into FIFO. Each element moves between stacks at most once, so despite the occasional O(n) transfer, the amortised cost per operation is O(1).

Deep explanation

A stack is LIFO and a queue is FIFO, so the trick is reversal — and pouring one stack into another reverses it exactly.

Python
class Queue:
    def __init__(self):
        self._in, self._out = [], []


    def enqueue(self, x):
        self._in.append(x)                 # always O(1)


    def dequeue(self):
        if not self._out:                  # only refill when EMPTY
            if not self._in:
                raise IndexError('dequeue from empty queue')
            while self._in:
                self._out.append(self._in.pop())
        return self._out.pop()

The single most important detail is the condition if not self._out. Transferring only when the outbox is empty is what makes the amortisation work. Transferring on every dequeue, or pouring back and forth, makes each operation O(n) and the whole thing pointless.

Why amortised O(1). Each element is pushed to the inbox once, popped from the inbox once, pushed to the outbox once, and popped from the outbox once — four operations over its lifetime, regardless of how many dequeues occur. Charge those four to the enqueue and every operation is O(1) amortised, even though an individual dequeue may cost O(n).

A useful way to state it in interview: the outbox holds the front of the queue in the correct order, and the inbox holds the back in reverse. Elements only ever migrate front-ward.

Worst case. A single dequeue after n enqueues costs O(n). If you need a worst-case O(1) guarantee — for a real-time system where one slow operation is unacceptable — this structure is unsuitable, and you would incrementally move one element per operation instead.

Real-world example

Enqueue 1, 2, 3, then dequeue twice, then enqueue 4 and dequeue again.

TypeScript
enqueue 1,2,3      in=[1,2,3]   out=[]
dequeue            out empty -> pour: in=[] out=[3,2,1]
                   pop -> 1     in=[]        out=[3,2]
dequeue            out non-empty, no pour
                   pop -> 2     in=[]        out=[3]
enqueue 4          in=[4]       out=[3]
dequeue            out non-empty -> pop -> 3  in=[4] out=[]

Note the last step: 4 was enqueued after 3 but sits in the inbox, so 3 is still correctly returned first. The invariant holds — the outbox always contains older elements than the inbox.

This mirrors a real pattern: a batching consumer drains a producer buffer in one go rather than element by element, amortising synchronisation cost across the batch.

Common mistakes

  • - Transferring from inbox to outbox on every dequeue instead of only when the outbox is empty, which makes every operation O(n).
  • - Pouring the outbox back into the inbox after each dequeue, destroying the ordering invariant and the amortisation.
  • - Claiming worst-case O(1)
  • it is amortised O(1) with an O(n) worst case for a single dequeue, and interviewers listen for that distinction.
  • - Forgetting to handle the empty case — both stacks empty must raise or return a sentinel, not pop from an empty list.
  • - Implementing `peek` by transferring and then popping, which discards the element
  • peek must inspect the outbox top without removing it.
  • - Computing size from only one stack
  • it is the sum of both.

Follow-up questions

  • Why is it amortised O(1) rather than O(n)?
  • How would you implement a stack using two queues instead?
  • Can this be made worst-case O(1)?
  • How do you implement peek correctly?

More Stacks interview questions

View all →