Problem Statement

Implement Queue using Stacks

Build a queue using only two stacks. A queue is a line, like people waiting at a checkout. The first one to get in line is the first one to leave. That order is called FIFO, which stands for first in, first out. A stack is the opposite. Picture a pile of plates: you add a plate to the top and take a plate from the top, so the last plate you put on is the first one you take off. That order is called LIFO, last in, first out. Our job is to make two stacks behave like one queue, supporting the usual queue actions: push (add to the back), pop (remove from the front), peek (look at the front), and empty (check if there is anything left).

easyStackStackTime: O(1) amortized for push and pop · Space: O(n)

Signals to notice

implement FIFO using two LIFO structuresamortized O(1) operationsdata structure design

Brute force first

Use one stack and move all elements on every dequeue — per operation. Every dequeue reverses the entire stack to access the bottom element. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Use two stacks: an 'inbox' for pushes and an 'outbox' for pops. Only transfer from inbox to outbox when outbox is empty. Each element is moved at most twice in its lifetime — amortized. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `ops=["MyQueue","push","push","peek","pop","empty"], args=[[],[1],[2],[],[],[]]`

MyQueue(): inbox=[], outbox=[]
push(1): inbox=[1], outbox=[]
push(2): inbox=[1,2], outbox=[]
peek(): outbox empty -> drain inbox -> inbox=[], outbox=[2,1]; return outbox top = 1
pop(): outbox not empty -> outbox.pop()=1; outbox=[2]; return 1
empty(): inbox=[] but outbox=[2] -> return false
returned outputs: [null,null,null,1,1,false]

What must stay true

The outbox always has elements in FIFO order (oldest on top). When it's empty, pour the inbox into it — this reversal converts LIFO to FIFO order. Elements are never moved back. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

push(x):            inbox.push(x)
peek()/pop():       if outbox is empty:
                        while inbox not empty: outbox.push(inbox.pop())
                    return outbox.top()  # pop() also removes it
empty():            return inbox empty AND outbox empty

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Transferring between stacks on every operation instead of only when the outbox is empty. The amortized guarantee depends on lazy transfer — move only when you must. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Stack Pattern