Implement Queue using Stacks
Easy· design· stack· queue
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
Input: push(1), push(2), peek(), pop(), empty()
Output: [null,null,1,1,false]
1 was pushed first, so it is at the front; 2 remains afterwards.
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)