DSA problem
Implement Queue using Stacks
Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue: push, peek, pop, and empty. You must use only standard stack operations — push to top, peek/pop from top, size, and is-empty — to manipulate the underlying stacks.
MyQueue() initializes the empty queue. push(x) pushes element x to the back of the queue. pop() removes the element from the front of the queue and returns it. peek() returns the element at the front of the queue. empty() returns true if the queue is empty, false otherwise.
The classic trick is to keep two stacks: an in stack for incoming pushes and an out stack from which pops and peeks read. When out is empty and a pop or peek is requested, we drain all of in into out — reversing the order so that the oldest element ends up on top of out. As long as we only drain when out is empty, every element is moved at most twice (once into in, once into out), giving amortized O(1) per operation even though individual transfers cost O(n).
You can apply this same amortization argument to many design problems where an "expensive" rebalancing step is rare enough that its cost spread across all operations is constant. The naive alternative — moving everything back and forth on every operation — gives the right answer but with O(n) per call, which is unacceptable in interview settings.
Examples
["MyQueue","push","push","peek","pop","empty"]
[[],[1],[2],[],[],[]][null,null,null,1,1,false]["MyQueue","push","pop","empty"]
[[],[5],[],[]][null,null,5,true]["MyQueue","push","push","push","pop","push","pop","pop","pop","empty"]
[[],[1],[2],[3],[],[4],[],[],[],[]][null,null,null,null,1,null,2,3,4,true]Constraints
- 1 <= x <= 9
- At most 100 calls will be made to push, pop, peek, and empty.
- All the calls to pop and peek are valid (the queue is not empty when called).
- You must use only standard stack operations.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.