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.
This approach uses two stacks: 'input' for pushing elements and 'output' for popping elements. While pushing, simply add the element to the input stack. For popping or peeking, check if the output stack is empty; if it is, transfer all elements from the input stack to the output stack and then pop or peek from the output stack.
The MyQueue class is implemented using two stacks. The 'input' stack holds elements pushed to the queue, and 'output' stack holds elements in the pop/peek order. The move_input_to_output helper method is used to transfer elements from input to output stack when output is empty, ensuring the correct order for queue operations.
Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue.
This approach is similar to the previous one, but emphasizes minimizing transfers between the stacks by only transferring when absolutely necessary (when the output stack is empty). This optimizes performance in terms of total operations.
Like the other solutions, this Java implementation leverages two stacks but specifically reduces data transfer by only moving elements from input to output when the output stack is empty. This ensures minimal effort when dequeue operations are scaffolded by stacked operations.
Java
JavaScript
Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue.
| Approach | Complexity |
|---|---|
| Two Stacks with Transfer on Pop | Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue. |
| Enhanced Two Stacks with Minimized Transfer | Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue. |
| 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 |
Implement Queue using Stacks - Leetcode 232 - Python • NeetCodeIO • 54,048 views views
Watch 9 more video solutions →Practice Implement Queue using Stacks with our built-in code editor and test cases.
Practice on FleetCode