Implement a queue with two stacks
Updated
inStack takes enqueues (push). outStack serves dequeues (pop). When outStack is empty, transfer all of inStack onto outStack. That reversal makes the oldest item the outStack top.
What to focus on
enqueue: in.push(x) O(1). dequeue: if out empty, transfer; then out.pop(). Amortized O(1) if each item transfers once. Peek is out.top after the same fill.
Worked examples
enqueue then dequeue
a = [], enqueue 4,1,9, dequeue- transfer 4,1,9 → out top 4
- pop 4
Result: dequeued 4, FIFO
partial out
a = [], after dequeue 4, dequeue again without new enqueues- out still has 1 then 9
Result: dequeued 1
enqueue after transfer
a = [], out has 1,9, enqueue 8- 8 goes to in
- next dequeues still 1 then 9 then 8
Result: FIFO held
Try it
Write enqueue(x) and dequeue(). x is the value to add at the back of the logical queue. enqueue pushes onto in. dequeue transfers in onto out if out is empty, then pops out. Never dequeue from in directly. Return the dequeued value. a = [], enqueue 4,1,9, dequeue → dequeued 4, FIFO. after dequeue 4, dequeue again without new enqueues → dequeued 1. out has 1,9, enqueue 8 → FIFO held.
You enqueue before the first dequeue. Values are integers. Dequeue only when at least one item is in in or out.