Implementing a queue with two stacks gives what cost per operation?
Options
- O(n) each
- O(1) amortized (Correct option)
- O(log n)
- O(n²) total
Answer
O(1) amortized
Why
Push new items onto stack in. To dequeue, pop from stack out; if out is empty, first move everything from in to out, which reverses the order so the oldest is on top.
A single move can be expensive, but each item is moved at most once in its life. Spread over all operations, the average cost is O(1): that is 'amortized' O(1).
Remember
Each item moves once → amortized O(1).