Implement Queue using Stacks
Problem statement
Build a first-in-first-out (FIFO) queue, but you're only allowed to use stacks internally — no list, deque, or queue from the language's library, just the standard stack operations: push something on top, look at or remove the top, check the size, and check if it's empty.
Implement a MyQueue class with:
push(x)— addsxto the back of the queue.pop()— removes and returns the value at the front of the queue.peek()— returns the value at the front without removing it.empty()— returnstrueif the queue holds nothing.
A stack only ever lets you reach the item you pushed most recently (last in, first out), which is the opposite order from a queue (first in, first out). The trick is arranging two stacks so that, from the outside, they still behave like one queue.
Examples
Example 1
Input: ["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output: [null, null, null, 1, 1, false]
Explanation: MyQueue() creates an empty queue. push(1) then push(2) leave the queue holding 1 then 2, with 1 at the front since it was pushed first. peek() returns 1 without removing it. pop() removes and returns 1, leaving only 2. empty() returns false because 2 is still there.
Hints
Approach
Optimal: Two stacks, amortized
Intuition
Instead of doing the reversal work on every push, do it lazily — only when
it's actually needed. Keep two stacks: inStack collects new pushes in
whatever order they arrive (newest on top), and outStack holds items in
front-to-back order (front on top), ready to be popped or peeked directly.
push is trivial: just add to inStack. When pop or peek is called and
outStack is empty, dump everything from inStack into outStack in one
go — this reverses their order exactly once, putting the oldest pushed item
on top. As long as outStack still has items left, later pop/peek calls
use it directly with no extra work. That's what makes it faster on average
than the brute-force approach: an item is only moved once per stack it
passes through, not on every single push.
Steps
- Keep two stacks,
inStackandoutStack, both empty at the start. push(x): pushxontoinStack— nothing else happens.- Before a
poporpeek: ifoutStackis empty, pop every item offinStackand push it ontooutStack(this reverses their order). pop()pops and returns the top ofoutStack;peek()looks at the top ofoutStackwithout removing it.empty()returns true only when bothinStackandoutStackare empty.
Dry run
push(1), push(2), push(3), pop(), push(4), pop(), pop(), pop():
| call | inStack | outStack | shift happens? | returns |
|---|---|---|---|---|
| push(1) | [1] | [] | no | — |
| push(2) | [1,2] | [] | no | — |
| push(3) | [1,2,3] | [] | no | — |
| pop() | [] | [3,2,1] | yes (outStack was empty) | 1 |
| push(4) | [4] | [3,2] | no | — |
| pop() | [4] | [3] | no (outStack not empty) | 2 |
| pop() | [4] | [] | no | 3 |
| pop() | [] | [] | yes (outStack was empty) | 4 |
Every value comes out in the order it was pushed — 1, 2, 3, 4 — even though
push(4) happened in the middle. Notice the shift only happens twice across
eight calls, which is what keeps the average cost low.
Edge cases: empty() has to check both stacks, since items can be waiting
in either one. pop/peek only trigger a shift when outStack is already
empty — if it still holds items from an earlier shift, they're used first,
which is what keeps the front-to-back order correct.
Complexity
Time Every - operation is amortized O(1). A single `pop` or `peek` can still cost O(n) on the rare call where a transfer happens, but each item only ever gets moved from `inStack` to `outStack` once across its whole lifetime in the queue, so the cost spreads out to O(1) per operation on average over many calls.
Space O(n) - the items are split between `inStack` and `outStack`, but together they still hold exactly the n items currently in the queue.
class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []
def push(self, x: int) -> None:
self.in_stack.append(x)
def _shift(self) -> None:
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def pop(self) -> int:
self._shift()
return self.out_stack.pop()
def peek(self) -> int:
self._shift()
return self.out_stack[-1]
def empty(self) -> bool:
return not self.in_stack and not self.out_stack
if __name__ == "__main__":
q = MyQueue()
out = [None]
q.push(1); out.append(None)
q.push(2); out.append(None)
out.append(q.peek())
out.append(q.pop())
out.append(q.empty())
print(out)RecapThe whole problem in a few lines, for the night before
- Spot it: build a FIFO queue from two LIFO stacks
- Idea: push to an input stack; on pop or peek, if the output stack is empty, move everything from input to output, which reverses the order
- Cost: O(1) amortized per operation, O(n) space
- Trap: only move items when the output stack is empty, or the order breaks
Interview follow-ups
Do the same thing in reverse: implement a stack using only queues.
Use two queues, or even a single queue. With one queue: to push
x, add it to the back as usual, then rotate the queue by dequeuing and re-enqueuing every element that was already there (allsize - 1of them) so thatxends up at the front. That makespushO(n) andpop/peek(just look at or remove the front) O(1) — the mirror image of the brute-force queue approach shown above.How would you make
push,pop,peekandemptysafe to call from multiple threads at once?Wrap access to
inStackandoutStackin a single lock (or use two separate locks with a fixed acquisition order to avoid deadlock), so that a shift frominStacktooutStackcan't happen in the middle of another thread readingoutStack. This turns amortized O(1) into amortized O(1) under contention, at the cost of threads blocking on each other during a shift — a lock-free version needs considerably more care to keep pushes, pops and shifts from corrupting each other.
Frequently asked questions
Any single pop or peek call can still trigger a full shift and cost
O(n) — amortized doesn't mean every call is fast. It means that if you add
up the cost of n operations total, the total work is O(n), because each item
only gets physically moved from inStack to outStack exactly once during
its entire time in the queue. Spread that one move across all the operations
touching that item, and the average per operation comes out to O(1).
That's a valid variant with the same overall behaviour: push becomes O(1)
(just push onto the stack) and the reversal work moves to pop/peek
instead. The two-stack version shown here is really that idea taken further
— it still does the reversal lazily, but keeps the already-reversed order
around in outStack so that a run of pops after a single shift stays
O(1) each, rather than re-reversing on every single pop.
It checks whether you understand the actual guarantees a data structure gives you, not just how to call its methods. The same skill — building a FIFO ordering out of a more restrictive primitive — comes up when a message broker only exposes LIFO semantics internally, or when you're limited to whatever operations a particular client library actually supports.
The problem's constraints guarantee that never happens (every pop/peek
call in the input is valid), so neither approach checks for it. In your own
production code you'd still want to raise a clear error or return an
Optional instead of letting pop() on an empty stack throw a raw runtime
exception.
