Watch 10 video solutions for Implement Stack using Queues, a easy level problem involving Stack, Design, Queue. This walkthrough by NeetCode has 99,180 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |