How do you implement a queue using two stacks? | Interview Question

Q: How do you implement a queue using two stacks?

**Target Audience:** Beginners preparing for coding interviews; you should know what a stack is. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the **Verified** section quotes the real output. ## 1. Why This Even Matters — A Story First A bakery has a tall, narrow tray rack that only opens at the top. Fresh trays go in on top, and if you take a tray out, you get the newest one. That is a stack. But customers should get the *oldest* bread first, which is how a queue works. The baker's trick: keep a second rack. When the counter needs bread and the second rack is empty, move every tray from the first rack into the second, one at a time. The newest tray, which was on top, goes in first and ends up at the bottom; the oldest tray ends up on top. Now the second rack

The problem

Question presented to candidate: "Implement a first-in, first-out queue in Python using only two stacks. Support push, pop, peek and empty, and tell me the time complexity of each operation."

What a strong answer should cover:

An inbox stack for pushes and an outbox stack for pops and peeks; pour inbox into outbox only when the outbox is empty.
Why pouring reverses the order so the oldest element is on top, and the invariant that pouring into a non-empty outbox would break.
Amortised O(1) per operation (each element moves at most once), worst case O(n) for a single pop.
The naive design that pours back after every pop is O(n) per pop.
Python specifics: lists as stacks with append/pop; in real code collections.deque is the queue to use, because list.pop(0) is O(n).

Clarifying questions expected:

"What should pop do on an empty queue: raise or return a sentinel?"
"Is amortised O(1) acceptable, or do you need a worst-case bound per call?"

Code / implementation expected: Yes — a small Python class with two lists.

stack
queue

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should know what a stack is. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the Verified section quotes the real output.

1. Why This Even Matters — A Story First

A bakery has a tall, narrow tray rack that only opens at the top. Fresh trays go in on top, and if you take a tray out, you get the newest one. That is a stack. But customers should get the oldest bread first, which is how a queue works.

The baker's trick: keep a second rack. When the counter needs bread and the second rack is empty, move every tray from the first rack into the second, one at a time. The newest tray, which was o

The solution is hidden so you can try first

11 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTwo-stack queue: trace every operation

Practice

PythonCounting element moves: lazy two-stack vs naive pour-back

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.