Watch 10 video solutions for Implement Stack using Queues, a easy level problem involving Stack, Design, Queue. This walkthrough by take U forward has 201,732 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 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.
| 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 |