Algorithms and Data Structures · Middle · Question 22 of 75
How do you implement a queue with two stacks so that each operation is amortized O(1)?
- 1Copy one stack into the other one on every enqueue
- 2Keep both stacks sorted and pop from the smaller one
- ✓Correct answer: Push to "in"; pop from "out", refilling it from "in" when empty
Explanation
Moving elements reverses their order, so the oldest ends up on top of "out". Each element is moved at most once, so n operations cost O(n) in total.