Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x) Pushes element x to the top of the stack.int pop() Removes the element on the top of the stack and returns it.int top() Returns the element on the top of the stack.boolean empty() Returns true if the stack is empty, false otherwise.Notes:
push to back, peek/pop from front, size and is empty operations are valid.
Example 1:
Input ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 2, 2, false] Explanation MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False
Constraints:
1 <= x <= 9100 calls will be made to push, pop, top, and empty.pop and top are valid.
Follow-up: Can you implement the stack using only one queue?
Problem Overview: Design a stack using standard queue operations only. The stack must support push, pop, top, and empty while maintaining LIFO behavior even though queues naturally operate in FIFO order.
The challenge is reversing the order of elements so the most recently pushed item always appears at the front when removing or peeking. Since queues only allow insertion at the back and removal from the front, the solution relies on rearranging elements during push or pop operations. Understanding the behavior of both stack and queue data structures is key.
Approach 1: Double Queue with Rearranging Elements (Push: O(n), Pop: O(1), Space: O(n))
This approach maintains two queues. When you perform push(x), insert the element into the second queue and then move every element from the first queue into it. This reorders the queue so the newest element always ends up at the front. After rearranging, swap the two queues so the main queue always stores elements in stack order.
Because the newest element stays at the front, both pop() and top() become simple queue front operations with constant time complexity. The tradeoff is that every push operation must iterate through all existing elements to maintain order. This design clearly demonstrates how queue operations can simulate stack behavior and is often the first approach candidates think of during interviews.
Approach 2: Single Queue with Rotation (Push: O(n), Pop: O(1), Space: O(n))
This optimized design uses only one queue. After inserting the new element at the back of the queue, rotate the queue so that the newly added element moves to the front. The rotation is done by repeatedly removing the front element and pushing it to the back for size - 1 iterations.
For example, after pushing a new element, cycle the previous elements behind it. This effectively reverses the queue order relative to insertion time, making the front of the queue behave like the top of a stack. As a result, pop() and top() simply read from the queue front in constant time.
This approach is cleaner because it eliminates the second queue while keeping the same complexity characteristics. It is commonly considered the optimal implementation for this problem and demonstrates strong understanding of queue manipulation and data structure design.
Recommended for interviews: The single queue rotation approach is usually preferred because it minimizes auxiliary data structures while preserving clear logic. Explaining the two-queue method first shows you understand the stack ordering problem, but implementing the single-queue rotation demonstrates stronger design skills and deeper mastery of queue operations.
This approach involves using two queues to simulate the operations of a stack. Whenever we push an element onto the stack, we move all elements from the first queue to the second queue, enqueue the new element into the first queue, and then move all elements back from the second queue to the first one. This ensures that the newest element is always at the front of the queue, allowing us to use single dequeue operations for pop() and top(), thus mimicking a stack's LIFO behavior.
The solution involves implementing two queues using arrays with helper functions for queue operations. We use these queues to implement stack operations where push is done by rotating elements between two queues, ensuring the stack order.
Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n) for two queues storing up to all stack elements at once.
This approach only uses one queue to implement the stack. When pushing an element, we enqueue the element and then rotate the queue such that the newly added element reaches the front. The queue thus behaves like a stack with respect to push, pop, top
This approach takes advantage of a single queue, rotating the elements until the newly pushed element reaches the front. This ensures it behaves as the top of the stack.
Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n), as we use only one queue to hold stack data.
We use two queues q_1 and q_2, where q_1 is used to store the elements in the stack, and q_2 is used to assist in implementing the stack operations.
push operation: Push the element into q_2, then pop the elements in q_1 one by one and push them into q_2, finally swap the references of q_1 and q_2. The time complexity is O(n).pop operation: Directly pop the front element of q_1. The time complexity is O(1).top operation: Directly return the front element of q_1. The time complexity is O(1).empty operation: Check whether q_1 is empty. The time complexity is O(1).The space complexity is O(n), where n is the number of elements in the stack.
| Approach | Complexity |
|---|---|
| Double Queue with Rearranging Elements | Time Complexity: |
| Single Queue with Rotation | Time Complexity: |
| Two Queues | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Double Queue with Rearranging Elements | Push: O(n), Pop: O(1) | O(n) | When clarity matters and you want a straightforward simulation using two queues |
| Single Queue with Rotation | Push: O(n), Pop: O(1) | O(n) | Preferred interview solution with minimal data structures |
Implement Stack using Queues - Leetcode 225 - Python • NeetCode • 99,180 views views
Watch 9 more video solutions →Practice Implement Stack using Queues with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor