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 such as push, pop, peek, and empty. A stack follows LIFO (last-in, first-out) behavior, while a queue follows FIFO (first-in, first-out). The challenge is to simulate stack behavior using one or more queues.
Approach 1: Double Queue with Rearranging Elements (Push O(n), Pop O(1))
This method uses two queues to maintain stack order. When you push a new element, insert it into an empty auxiliary queue first. Then move all elements from the main queue into the auxiliary queue. Finally, swap the queue references. This rearrangement ensures the most recently pushed element always stays at the front of the main queue, allowing pop and top to run in constant time. The key idea is forcing the queue to behave like a stack by reordering elements during insertion. Each push requires moving up to n elements, resulting in O(n) time complexity, while pop, top, and empty run in O(1) time. Space complexity is O(n) due to storing elements across two queues.
Approach 2: Single Queue with Rotation (Push O(n), Pop O(1))
This approach uses only one queue and relies on rotation to simulate stack behavior. After inserting a new element into the queue, rotate the existing elements by repeatedly dequeuing the front element and enqueuing it at the back. Perform this rotation size - 1 times so the newly inserted element moves to the front of the queue. With this arrangement, the queue's front always represents the stack's top. As a result, pop and top operations take O(1) time, while push takes O(n) because of the rotations. Space complexity remains O(n) since all elements reside in a single queue.
Both strategies rely on manipulating queue order to maintain the LIFO property of a stack while only using operations available in a queue. This makes the problem a classic example of data structure transformation and design questions often used in interviews.
Recommended for interviews: The single queue rotation approach is usually preferred because it uses fewer data structures while maintaining the same asymptotic complexity. Interviewers often want to see whether you recognize that rotating the queue after each insertion effectively places the newest element at the front. Showing the two-queue version first demonstrates understanding of the LIFO requirement, while the single-queue optimization shows stronger design intuition.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Double Queue with Rearranging Elements | Time Complexity: |
| Single Queue with Rotation | Time Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Double Queue with Rearranging Elements | Push: O(n), Pop/Top: O(1) | O(n) | Clear conceptual approach when demonstrating how queue order can be manipulated to mimic stack behavior |
| Single Queue with Rotation | Push: O(n), Pop/Top: O(1) | O(n) | Preferred interview solution when minimizing extra data structures |
Stack Implementation using a Single Queue • take U forward • 201,732 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