212. Implement Queue using Stacks
A queue hands elements back in arrival order (FIFO); a stack hands back the most recent one (LIFO). Your job is to fake the first using only the second: build a class MyQueue whose internals are nothing more than two ordinary stacks.
Implement four methods:
push(x)— place integerxat the back of the queue.pop()— remove the element at the front of the queue and return it.peek()— return the front element without removing it.empty()— returntruewhen the queue holds nothing,falseotherwise.
The only moves you may make on your internal storage are legal stack moves: push onto the top, pop the top, read the top, and ask for size/emptiness. No indexing into the middle, no deques.
Every pop and peek you receive is guaranteed to arrive while the queue is non-empty.
Follow-up: can you make every operation cost amortized O(1) — so any sequence of n operations does O(n) total work?
Example 1:
Input: MyQueue() · push(1) · push(2) · peek() · pop() · empty()
Output: 1, 1, false
Explanation: 1 arrived before 2, so both peek and pop see 1 first. After removing it, 2 is still queued, so empty() is false.
Example 2:
Input: push(5) · pop() · empty() · push(7) · push(9) · peek()
Output: 5, true, 7
Explanation: 5 goes in and straight back out, leaving the queue empty. Then 7 and 9 arrive; 7 is older, so peek() reports 7.
Constraints:
- 1 ≤ q ≤ 10⁴ operations
- -10⁹ ≤ x ≤ 10⁹
- Every pop and peek is issued while the queue is non-empty.
- Internal storage may only be used through stack operations: push-to-top, pop-from-top, read-top, size/isEmpty.
Hints:
Pouring a stack element-by-element into a second stack reverses its order. What order do you get if the elements went in newest-on-top?
Keep an *inbox* stack for arrivals and an *outbox* stack for departures. Only when the outbox is empty do you pour the whole inbox into it — each element migrates at most once, so the total work stays linear.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: MyQueue() · push(1) · push(2) · peek() · pop() · empty()
Expected output: 1, 1, false