Implement Queue Using Stacks
Module 9 · Queues
Problem
Implement a FIFO queue — push, pop, peek, empty — using only
two stacks (only push-to-top, pop-from-top, peek, isEmpty allowed on
them). Amortized O(1) per operation required.
Examples
Example 1
Input
push(1), push(2), peek()Output1Explanation. FIFO: the first pushed
Example 2
Input
pop()Output1Example 3
Input
empty()OutputfalseConstraints
≤ 100 operations · calls are always valid.
Attempt it first
A classic for a reason: it tests whether amortized analysis is something you can produce, not just consume. The naive version (make every push keep order) works but does O(n) per push. The good version does better by being lazier. Find the laziness.