Maintained by Vikas Dulgunde, 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.
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.
Visible test cases
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.
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.
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.
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.
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.