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?
The goal of #225 Implement Stack using Queues is to simulate the behavior of a stack (LIFO: Last In, First Out) using one or more queues (FIFO: First In, First Out). Since stacks remove the most recently added element while queues remove the oldest, we must carefully rearrange queue elements to mimic stack behavior.
A common approach uses two queues. When performing a push operation, elements can be transferred between queues so that the newest element always stays at the front of the active queue. This ensures that the pop operation behaves like a stack and returns the most recently pushed element.
An alternative and cleaner method uses a single queue. After inserting a new element, the queue is rotated by moving earlier elements to the back. This effectively brings the newly inserted element to the front, preserving stack order.
Both strategies rely on queue operations like enqueue and dequeue. The design trade-off usually affects the cost of push versus pop, while maintaining O(n) worst‑case operations and O(n) space for storing elements.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Queues (Push Costly) | Push: O(n), Pop: O(1), Top: O(1) | O(n) |
| Single Queue with Rotation | Push: O(n), Pop: O(1), Top: O(1) | O(n) |
take U forward
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE
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.
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
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Rotation moves previously inserted elements behind the newly added element. This ensures the newest element becomes the first to be removed, which matches the LIFO behavior required for stack operations.
Yes, this type of design problem is common in technical interviews, including FAANG companies. It tests understanding of fundamental data structures and how to adapt one structure to mimic another.
A popular approach uses a single queue and rotates elements after each push so the newest element appears at the front. This ensures stack-like behavior where pop returns the most recently inserted element. The push operation becomes O(n) while pop remains O(1).
The problem specifically requires using queues to simulate a stack. Using either one queue with element rotation or two queues for element rearrangement is the typical design approach to achieve LIFO behavior.
In Python, a single deque is manipulated to current element to the front within the push operation. Other operations remain direct, simulating stack functions through queue operations.