Implement Queue using Stacks - Solution & Explanation
Problem Statement
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()Returnstrueif the queue is empty,falseotherwise.
Notes:
- You must use only standard operations of a stack, which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
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 <= 9- At most
100calls will be made topush,pop,peek, andempty. - All the calls to
popandpeekare 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.
Approach Overview
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 1: Two Stacks with Transfer on Pop
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.
Complexity
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 2: Enhanced Two Stacks with Minimized Transfer
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.
Code
Java
JavaScript
Complexity
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 3: Double Stack
We use two stacks, where stk1 is used for enqueue, and another stack stk2 is used for dequeue.
When enqueueing, we directly push the element into stk1. The time complexity is O(1).
When dequeueing, we first check whether stk2 is empty. If it is empty, we pop all elements from stk1 and push them into stk2, and then pop an element from stk2. If stk2 is not empty, we directly pop an element from stk2. The amortized time complexity is O(1).
When getting the front element, we first check whether stk2 is empty. If it is empty, we pop all elements from stk1 and push them into stk2, and then get the top element from stk2. If stk2 is not empty, we directly get the top element from stk2. The amortized time complexity is O(1).
When checking whether the queue is empty, we only need to check whether both stacks are empty. The time complexity is O(1).
Complexity Comparison
| 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. |
| Double Stack | — |
Detailed Complexity 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 |
Video Solution
Implement Queue using Stacks - Leetcode 232 - Python • NeetCodeIO • 57,935 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Implement Queue using Stacks easy or hard?
Implement Queue using Stacks Python/Java solution
How to solve Implement Queue using Stacks in O(n)?
What is the best approach for Implement Queue using Stacks?
Is Implement Queue using Stacks asked at Google/Amazon/Meta?
What data structure is used in Implement Queue using Stacks?
What is the time complexity of Implement Queue using Stacks?
Ready to solve this problem?
Practice Implement Queue using Stacks with our built-in code editor and test cases.
Practice on FleetCode