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. The challenge is that stacks are LIFO while queues are FIFO, so you must simulate FIFO behavior using stack operations.
Approach 1: Two Stacks with Transfer on Pop (O(n) worst-case per pop, O(n) space)
This method uses two stacks: an input stack for push operations and an output stack for queue order. When pop or peek is called, move every element from the input stack to the output stack. This reversal converts the LIFO order into FIFO order. After the transfer, the top of the output stack represents the front of the queue. The downside is that every pop may require moving all elements, giving O(n) time in the worst case and O(n) space for the two stacks.
Approach 2: Enhanced Two Stacks with Minimized Transfer (Amortized O(1), O(n) space)
This optimized design still uses two stacks but only transfers elements when necessary. New elements always go into the input stack. When pop or peek is requested, check the output stack first. If it is empty, move all elements from the input stack to the output stack once. Because each element moves between stacks at most one time, the cost spreads across operations, giving amortized O(1) time per operation and O(n) space.
The key insight is that reversing order once is enough to maintain queue behavior until the output stack empties. This avoids repeated transfers and drastically improves performance compared to the naive approach.
Both solutions rely on understanding how a stack can reverse order and how that reversal helps simulate a queue. The problem is also a classic data structure design exercise where you combine existing primitives to build a new abstraction.
Recommended for interviews: Interviewers usually expect the optimized two-stack solution with amortized O(1) operations. Showing the basic transfer-on-pop idea first demonstrates that you understand how stacks reverse order. Then refining it to minimize transfers shows stronger algorithmic thinking and system design awareness.
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.
C++
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.
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 O(n) | O(n) | Simple implementation when operation frequency is small |
| Enhanced Two Stacks with Minimized Transfer | Amortized O(1) | O(n) | Interview preferred approach and general production design |
Implement Stack using Queues - Leetcode 225 - Python • NeetCode • 79,902 views views
Watch 9 more video solutions →Practice Implement Queue using Stacks with our built-in code editor and test cases.
Practice on FleetCode