Build a queue out of two stacks

Stacks and queues Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
inbox, outbox = [1, 2, 3], []
while inbox:
    outbox.append(inbox.pop())
print(outbox, outbox[-1])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [3, 2, 1] 1

Right: moving reverses the order, so the oldest item, 1, is on top.

One reversal puts the oldest item on top of the outbox, which is what a queue needs to hand out next.

Why not the others?
  • B [1, 2, 3] 3. Popping from the inbox takes 3 first, so the order flips.
  • C [3, 2, 1] 3. The top of a list-based stack is its last item, which is 1.

30-second answer

Push onto an 'inbox' stack. To pop or peek, take from an 'outbox' stack; if it is empty, move everything from the inbox to the outbox first, which reverses the order so the oldest item ends on top. Each item moves at most once, so every operation is amortised O(1); the two stacks take O(n) space.

Practise saying it · 45 s. No recording, just a timer

Explain a queue built from two stacks.

Say your answer out loud, then check which of these points you covered:

  • Inbox and outbox
  • Move only when outbox is empty
  • Amortised O(1)

Deep dive

Only refill the outbox when it is empty; refilling early breaks the order.

The amortised argument: each item is pushed twice and popped twice in total.

This is how some functional languages build persistent queues.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def run_two_stack_queue(ops: list[str]) -> list[int]:
    inbox: list[int] = []
    outbox: list[int] = []
    out = []
    for op in ops:
        if op.startswith("push "):
            inbox.append(int(op[5:]))
            continue
        if not outbox:
            while inbox:
                outbox.append(inbox.pop())
        out.append(outbox.pop() if op == "pop" else outbox[-1])
    return out

Common mistakes

  • Moving items back to the inbox after every pop, which makes operations O(n).
  • Refilling the outbox while it still has items.

Senior take & follow-ups

Explain the 'move only when empty' rule and the amortised cost together.

Follow-up questions

Think of your answer first, then open the hint.

  1. What about a stack from two queues?

    Show hint

    Possible, but one operation becomes O(n).

  2. Why not just use a deque?

    Show hint

    In real code you would; the question tests amortised reasoning.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.