vizlearn

Implement a queue using two stacks

Interview QuestionsBy Updated

Two stacks: push onto the inbox, pop from the outbox. When the outbox is empty, pour the whole inbox into it — which reverses the order, turning LIFO into FIFO. Pouring only when empty is what makes dequeue O(1) amortised; pouring every time makes it O(n).

Stacks & queuesCoding problemEasy

Step through it

What to watch

  • Enqueue never reorders anything — it is always one push.
  • The pour happens only when the outbox is empty, and it reverses the order.
  • While the outbox has items, dequeue does no moving at all.

Say this out loud

"One stack for incoming, one for outgoing. Enqueue pushes onto the inbox. Dequeue pops the outbox, and if the outbox is empty first it moves everything across, which reverses the order into FIFO. Enqueue is O(1); dequeue is O(1) amortised, because each element moves between the stacks exactly once in its lifetime, even though a single dequeue can be O(n)."

Overview

A queue returns items in first-in, first-out order; a stack returns them last-in, first-out. Two stacks can implement a queue by reversing the inbox into an outbox only when the outbox is empty, preserving amortised O(1) operations.

Run it

FIFO through interleaved operations, which is the part worth checking.

1Python
Output
The cost of the emptiness check, measured on the same workload.
2Python
Output
The eager version that pours back and forth on every call does the same job, but far more of the work.
3Python
Output
One dequeue can still be O(n) - amortised is a claim about the total.
4Python
Output

                

                

                    
Why reversing twice gives FIFO

                    
A stack reverses what you put into it. Pour one stack into another and you have reversed it again, which restores the original order — so the item pushed first ends up on top of the second stack, which is exactly the front of a queue.
That is the whole trick, and it is worth stating in one sentence in an interview: the inbox has them newest-first, the outbox has them oldest-first, and pouring is what converts between the two.

                

                

                    
The emptiness check is the entire complexity argument

                    
The naive version pours on every dequeue — and, to keep enqueue working, pours back afterwards. That is O(n) per call and O(n²) for n dequeues. The editor below measures it: 400 operations cost 160,000 moves that way, against 400 the right way.
Pouring only when the outbox is empty means each element crosses once in its entire life. Total moves for n items is n, so the average cost per dequeue is constant even though one individual dequeue can touch every element. That is amortised O(1), and the distinction between "amortised O(1)" and "O(1) worst case" is what the follow-up question is about.

                

                

                    
When amortised is not good enough

                    
Amortised bounds are about totals, and some systems care about the worst single call. A real-time audio callback or a request with a latency budget cannot afford the one dequeue that moves ten thousand items, even if the average is fine.
The honest answer is that this structure cannot fix that — and naming the alternatives is what a strong answer does. Move a constant number of items per operation instead of all of them (incremental rebuilding), or use a structure that is O(1) worst case outright, which in Python is collections.deque. Which leads to the real-world footnote: nobody builds a queue from two stacks in production. The question is about reasoning, and it is fair to say so while still answering it.

                

                

                    
The mirror question

                    
"Now implement a stack using two queues." It is the same idea and strictly worse: one of the two operations has to become O(n), because a queue gives you the wrong end and no amount of shuffling amortises away. Either push moves everything into the second queue behind the new item, or pop moves n−1 items across to reach the last one.
There is no trick that makes both O(1) here, and saying that directly is the right answer — the asymmetry between the two questions is the thing being tested.

                

                

                    
Edge cases to raise

                    
Volunteering these is most of what separates a correct answer from a good one.
Dequeue from empty. The outbox is empty and so is the inbox, so the pour moves nothing and the pop raises. Check it explicitly rather than letting an IndexError escape from an internal list.
peek() needs the same pour. Forgetting the emptiness check there is the standard bug in the extension, and it returns the newest item instead of the oldest.
Nobody ships this. collections.deque is O(1) at both ends and is what production code uses. Saying that while still answering the question shows you know why it is being asked.

                

                

                    
Sources and next steps

                    
                

            


        

    



How the code works
FIFO order demonstrated through interleaved operations, then the move counts for the amortised and the eager versions at 400 operations each.
How the code works
  1. if not self.outbox:The line the whole question turns on. Pouring unconditionally is correct and O(n) per call; pouring only when empty is correct and O(1) amortised.
  2. self.outbox.append(self.inbox.pop())Popping from one and pushing to the other is the reversal. After the pour, the oldest item is on top of the outbox.
  3. inst.moves400 against 160,000 for the same workload. The counter is in the class so the difference is a measurement rather than a claim about big-O.
  4. a single dequeue after 1,000 enqueues1,000 moves on that call and 0 on the next. Amortised O(1) is a statement about the total, and this is what it looks like from inside.
Change one thing
  • Add peek(). It needs the same emptiness check as dequeue, and forgetting it is the standard bug in this extension.
  • Try implementing a stack from two queues and count the moves. One of the two operations stays O(n) however you arrange it, which is the asymmetry worth being able to explain.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. Why does pouring one stack into the other give FIFO order?
  2. What makes dequeue O(1) amortised rather than O(n)?
  3. What is the cost of a single worst-case dequeue?
  4. Implementing a stack from two queues instead:




        
    



 Cheat sheet
Implement a queue using two stacks
Build a FIFO queue from two stacks. Push onto one, pop from the other, and see why every element moves at most twice for amortized O(1) cost.
INTERVIEW · vizlearn.in/interview/queue-from-two-stacks.html
More in Interview
InterviewTop k frequent elementsInterviewMerge k sorted sequencesInterviewFind the median of a data streamInterviewWrite binary search without an off-by-one
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact