Implement Queue Using Two Stacks
Maintained by Vikas D, software engineer
A stack hands back the most recently added item first, but a queue must hand back the oldest item first. The challenge is to recover that oldest-first behaviour using nothing but stack operations: push onto the top, pop off the top, and read the top.
Rather than calling methods on an object, this version feeds the calls to you as data. You get an array of operation names and a parallel array of argument lists. A "push" carries the number to enqueue in its argument list; "pop", "peek", and "empty" each carry an empty list.
Step through the operations in order and build an array of results, one entry per call. A "push" returns null, a "pop" returns and removes the value at the front of the queue, a "peek" returns that front value without removing it, and an "empty" returns true when the queue holds nothing and false otherwise.
You are guaranteed that pop and peek only run while the queue has at least one element, so there is no empty-queue edge case to guard against on those two calls.
Examples
Enqueue 1 then 2. The front of the queue is 1, so peek reports 1 and the following pop also returns 1 and removes it. With 2 still waiting, empty reports false.
Three values go in as 1, 2, 3. The pops come back in that same arrival order, confirming FIFO behaviour, and once all three leave the queue is empty.
Push 5 then immediately pop it back out. Push 7 and 9; the next pop removes 7 (the older of the two), leaving 9 as the front that peek then reports.
Constraints
- 1 <= val <= 9 for every pushed value.
- At most 100 operations are issued in total.
- pop and peek are only ever called on a non-empty queue.
- Only stack-style access is allowed for the underlying storage: add to the top, remove from the top, and read the top.
Visible test cases
- myQueue(["push","push","peek","pop","empty"], [[1],[2],[],[],[]]) == [null,null,1,1,false]
- myQueue(["push","push","push","pop","pop","pop","empty"], [[1],[2],[3],[],[],[],[]]) == [null,null,null,1,2,3,true]
- myQueue(["push","pop","push","push","pop","peek"], [[5],[],[7],[9],[],[]]) == [null,5,null,null,7,9]
- myQueue(["push","empty","pop","empty"], [[1],[],[],[]]) == [null,false,1,true]
Hints
Hint 1
A single stack reverses arrival order. If you pour every element from one stack into a second one, item by item, the order flips a second time and the oldest element ends up on top, ready to be served.
Hint 2
You do not have to refill the queue after every removal. Keep two stacks: one that receives new pushes, and one that you serve pops and peeks from. Only the serving stack ever produces output.
Hint 3
Refill the serving stack from the incoming stack only when the serving stack is empty. Doing it lazily, rather than on every operation, is what keeps the amortized cost per call constant.
Approaches
Reshuffle on every read
Time O(n) per push, O(1) per pop, peek, empty · Space O(n)Keep the queue in one stack with the front always sitting at the bottom, and dig it out by emptying into a helper stack whenever you need the front.
- On push, dump everything into a helper stack, place the new value, then pour it all back so the newest sits at the bottom.
- Pop and peek then simply act on the top of the main stack, which is the oldest element.
- empty checks whether the main stack has any elements.
Two stacks with lazy transfer
Time O(1) amortized per operation · Space O(n)Split the work across an inbound stack that collects pushes and an outbound stack that serves reads, only moving elements across when the outbound stack runs dry.
- Keep an inbound stack and an outbound stack.
- push always lands on the inbound stack.
- For pop or peek, if the outbound stack is empty, pour the whole inbound stack onto it so arrival order is reversed and the oldest element is now on top.
- pop removes the outbound top, peek reads it without removing.
- empty is true only when both stacks are empty.
Common mistakes
- Transferring the inbound stack to the outbound stack while the outbound stack still has elements. That interleaves old and new arrivals and breaks FIFO order, so only move when the outbound stack is empty.
- Refilling the outbound stack on every pop instead of only when it is empty, which silently turns an amortized O(1) design into O(n) per call.
- Checking only one stack for emptiness. The queue is empty only when both stacks are empty; an element may be sitting on either side at any time.
- Reaching into the middle or bottom of a stack to find the front. The whole point is to use only top-of-stack access, so the front has to be exposed by transferring, not by indexing.
- Returning a result for push or for empty in the wrong slot. Only push contributes null, while empty contributes a boolean.
Follow-up variations
- Implement a stack out of two queues, the mirror-image problem, and compare which operation becomes the expensive one.
- Support a peek-at-back operation that returns the most recently enqueued value, and decide which stack already holds that answer.
- Bound the queue to a fixed capacity and reject or signal pushes once it is full.
- Discuss how concurrent push and pop from different threads would race on the lazy transfer and what locking would make it safe.