Implement Queue using Stacks
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Build a first-in-first-out queue that supports push, pop, peek and empty, using only standard stack operations underneath. Aim for amortised O(1) per operation.
Examples
Constraints
- • 1 <= x <= 9
- • At most 100 calls
- • pop and peek are only called on a non-empty queue
Hints & approach
Hint 1
Pouring one stack into another reverses the order of its elements.
Hint 2
Use one stack for incoming items and another for outgoing items.
Hint 3
Only refill the outgoing stack when it is empty.
Approachtry the hints first
Keep an in-stack and an out-stack. push always goes onto the in-stack. For pop or peek, if the out-stack is empty, move everything from the in-stack onto it, which flips the order so the oldest item is on top; then read or pop the top. Each element is moved at most once, so the amortised cost per operation is O(1). empty is true when both stacks are empty.
Time O(1) amortised · Space O(n)
