Watch 10 video solutions for Implement Queue using Stacks, a easy level problem involving Stack, Design, Queue. This walkthrough by NeetCode has 79,902 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
Implement the MyQueue class:
void push(int x) Pushes element x to the back of the queue.int pop() Removes the element from the front of the queue and returns it.int peek() Returns the element at the front of the queue.boolean empty() Returns true if the queue is empty, false otherwise.Notes:
push to top, peek/pop from top, size, and is empty operations are valid.
Example 1:
Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false] Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
Constraints:
1 <= x <= 9100 calls will be made to push, pop, peek, and empty.pop and peek are valid.
Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.
Problem Overview: Design a queue using only stack operations. The queue must support push, pop, peek, and empty. A queue is FIFO (first-in, first-out) while a stack is LIFO, so the core challenge is reversing the order of elements using stack behavior.
Approach 1: Two Stacks with Transfer on Pop (Push O(1), Pop O(n) time, O(n) space)
Maintain two stacks: input and temp. Every push operation simply pushes the element onto the input stack, which keeps insertion O(1). When you need to pop or peek, move elements from input to temp until one element remains. That last element represents the front of the queue. After retrieving it, move the remaining elements back. This works because transferring elements reverses their order, effectively simulating FIFO behavior using stack operations.
The tradeoff is performance. Each pop or peek may require moving up to n elements twice, leading to O(n) time in the worst case. Space complexity remains O(n) since both stacks together store the same elements. This approach is simple to reason about and clearly demonstrates how order reversal works when implementing a queue with stacks.
Approach 2: Enhanced Two Stacks with Minimized Transfer (Amortized O(1) time, O(n) space)
This optimized design still uses two stacks, usually called inStack and outStack. Push operations go directly into inStack. When a pop or peek is requested, check whether outStack is empty. If it is, transfer all elements from inStack to outStack by repeatedly popping from one and pushing into the other. That single transfer reverses the order so the oldest element ends up on top of outStack.
Subsequent pop or peek operations read directly from outStack without additional transfers. Each element moves between stacks at most once, which gives an amortized time complexity of O(1) for all queue operations. Space complexity stays O(n) since the stacks store the same set of elements. This pattern appears frequently in design problems where one data structure must emulate another.
Recommended for interviews: Interviewers usually expect the optimized two‑stack solution with amortized O(1) operations. Showing the simple transfer-on-pop approach first demonstrates understanding of order reversal. Then improving it with a lazy transfer strategy shows stronger algorithmic reasoning and awareness of amortized analysis.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Stacks with Transfer on Pop | Push O(1), Pop/Peek O(n) | O(n) | When demonstrating the basic idea of reversing order with stacks or for simpler conceptual explanations |
| Enhanced Two Stacks with Minimized Transfer | Amortized O(1) for all operations | O(n) | Preferred solution for interviews and production since each element is moved between stacks at most once |