Author at SyntaxFlow
Welcome to a deep dive into one of the most classic and frequently asked data structure questions in technical interviews: Implement Stack Using Queues (LeetCode 225).
Whether you are a college student preparing for campus placements, a beginner stepping into the world of Data Structures and Algorithms (DSA), or a seasoned developer brushing up on LeetCode, this article is designed for you. We will break down this problem from first principles, explore multiple approaches, visualize the algorithms, and prepare you to confidently tackle this in a real interview.
Let’s get started!
Before we jump into the code, let's briefly review the two main characters of our story:
Why is this problem so popular in interviews? At first glance, implementing a stack using a queue sounds counterintuitive. You are essentially trying to make a FIFO structure behave like a LIFO structure. Interviewers love this question because it doesn't require knowing obscure algorithms. Instead, it tests your fundamental understanding of how data structures operate, your logical reasoning, and your ability to manipulate data flow creatively.
The Goal: You need to implement a Last-In-First-Out (LIFO) stack using only the standard operations of a First-In-First-Out (FIFO) queue.
You are required to implement the MyStack class with the following standard stack operations:
push(int x): Pushes element x to the top of the stack.pop(): Removes the element on the top of the stack and returns it.top(): Returns the element on the top of the stack without removing it.empty(): Returns true if the stack is empty, false otherwise.Note: You must use only standard operations of a queue. This means onlypush to back,peek/pop from front,size, andis emptyoperations are allowed.
When faced with a constraint (like a queue pulling from the front instead of the back), a common problem-solving technique is to use an extra buffer. In this case, we can use a second queue to help us reorganize the elements.
To make a queue act like a stack, we need the most recently added element to always be at the front of the queue. That way, when we call pop() or top(), we instantly get the LIFO element.
How do we force the newest element to the front? By using a primary queue (q1) and a helper queue (q2). When a new element arrives, we temporarily store it in q2. Then, we take all the existing elements from q1 (which are in the correct LIFO order) and enqueue them behind the new element in q2. Finally, we swap the names of q1 and q2.
Push Operation (push(x)):
x to the empty helper queue, q2.q1 and push them into q2.q1 and q2. Now q1 holds the elements in the correct LIFO order, and q2 is empty and ready for the next operation.Pop, Top, and Empty Operations: Since q1 is perfectly arranged as a stack, these operations are straightforward:
pop(): Simply remove and return the front element of q1.top(): Just return the front element of q1.empty(): Check if q1 is empty.#include <queue>
using namespace std;
class MyStack {
private:
queue<int> q1;
queue<int> q2;
public:
MyStack() {
// Constructor
}
void push(int x) {
// Step 1: Push the new element to q2
q2.push(x);
// Step 2: Transfer all elements from q1 to q2
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
// Step 3: Swap q1 and q2
swap(q1, q2);
}
int pop() {
int topElement = q1.front();
q1.pop();
return topElement;
}
int top() {
return q1.front();
}
bool empty() {
return q1.empty();
}
};Advantages:
pop() and top() operations are blazing fast (O(1)).Disadvantages:
push operation is slow (O(n)) because of the constant data transfer between q1 and q2.Can we do better? In an interview, once you present the two-queue solution, the interviewer will almost certainly ask: "Can you implement this using only ONE queue?"
The answer is yes. We can eliminate the extra space of the second queue by leveraging a technique called Queue Rotation.
A queue processes elements in a circle-like fashion if we dequeue from the front and immediately enqueue back to the rear.
When we push a new element into a single queue, it naturally goes to the back. But for a stack, we want this newest element at the front.
To achieve this, we can take the elements sitting in front of our newly added element, pop them off one by one, and push them right back into the queue. If we do this exactly times (where is the new size of the queue), our newest element rotates its way to the front!
Push Operation (push(x)):
size. (This represents the elements currently in the queue).x into the queue.size times:Pop, Top, and Empty Operations:
These remain exactly the same as Approach 1. The front of the queue always holds the top of our stack.
Let's visualize the rotation for push(3) when the queue already has [2, 1].
#include <queue>
using namespace std;
class MyStack {
private:
queue<int> q;
public:
MyStack() {
// Constructor
}
void push(int x) {
// Record the size before pushing the new element
int size = q.size();
// Push the new element to the back
q.push(x);
// Rotate the previous elements behind the new element
for (int i = 0; i < size; ++i) {
q.push(q.front());
q.pop();
}
}
int pop() {
int topElement = q.front();
q.pop();
return topElement;
}
int top() {
return q.front();
}
bool empty() {
return q.empty();
}
};advantages:
Disadvantages:
push is still O(n).Here is a quick snapshot summarizing both approaches.
If the rotation logic still feels like magic, let's look at it conceptually using plain text.
A queue operates like a conveyor belt. If you take an item off the front of the belt and drop it back onto the end of the belt, the order of items changes relative to the "front", but the cyclic sequence remains intact.
Imagine a queue with elements [A, B, C] (A is at the front).
You want to add D so that it behaves like a stack (so D should be the new front).
D to the back:Front -> [A, B, C, D] <- BackA to the back:Front -> [B, C, D, A] <- BackB to the back:Front -> [C, D, A, B] <- BackC to the back:Front -> [D, A, B, C] <- BackBy rotating exactly times (where is the original size 3), D perfectly lands at the front of the queue, while the rest of the elements retain their relative LIFO order!
A high-quality interview answer always considers edge cases. Here are a few to keep in mind:
pop() or top() is called on an empty stack? In standard C++ STL, calling front() or pop() on an empty queue results in undefined behavior. While LeetCode guarantees valid test cases (you won't be asked to pop from an empty stack), in a real-world scenario, you should add a check: if (empty()) throw runtime_error("Stack is empty");.size evaluates to 0 during push. The loop for (int i = 0; i < 0; ++i) simply won't execute, which is perfectly correct. The single element remains at the front.When coding this under the pressure of a whiteboard interview, candidates often make the following errors:
int size = q.size(); after q.push(x);, your loop will run one time too many, pushing the newly added element itself to the back!<= size instead of < size in the for loop causes the same problem as above.q1 and q2 at the end of the push operation leaves your elements stranded in the helper queue.pop() on a newly instantiated MyStack.💡 Pro-Tip: Never jump straight to the single-queue optimal solution unless you are running out of time.
push instead of pop. In that approach, push just adds to the back of the queue (O(1)). But for pop, you would have to rotate the queue times right before popping, making pop O(N). Which one is better depends on the system’s read/write ratio.Here are some frequently asked questions regarding this problem:
1. Can a stack really be implemented using only one queue?
Yes, by using the queue rotation technique. We repeatedly pop elements from the front and push them to the back, essentially reversing the FIFO order into LIFO.
2. Why is the push operation O(n) instead of O(1)?
Because queues only allow adding to the back and removing from the front. To get the newest element to the front, we must physically move all the older elements behind it, taking O(n) time.
3. Why isn't the pop operation O(n)?
Because we do all the heavy lifting during the push phase. By the time push finishes, the queue is already arranged in perfect LIFO order. Therefore, pop just needs to remove the front element, taking O(1) time.
4. Which approach is preferred in an interview?
The One Queue approach is the optimal and expected final answer. However, demonstrating the Two Queue approach first is highly recommended to show your thought process.
5. Is this question actually asked in interviews?
Absolutely. It is a classic phone-screen and entry-level interview question at major tech companies (FAANG) to test your fundamental grasp of data structures.
6. Can a deque (Double Ended Queue) solve this?
Yes, a deque allows pushing and popping from both ends. However, the constraints of this specific LeetCode problem strictly forbid using deque-specific operations (like push_front). You are only allowed to use standard FIFO queue operations.
7. What exactly is "queue rotation"?
Queue rotation is the act of removing the element at the front of the queue and immediately inserting it at the back of the same queue.
8. Is recursion involved in solving this?
No, recursion is not required. However, you could technically simulate a stack using a queue and the implicit call stack (recursion), but it defeats the purpose of the problem since the call stack is just another stack!
9. Can we optimize the time complexity further?
Using strictly one or two queues with standard queue operations, it is impossible to have both push and pop be O(1) simultaneously. One of them must be O(N).
10. What are similar interview questions to practice?
If you enjoyed this, you should immediately practice its twin problem: Implement Queue using Stacks (LeetCode 232).
video reference:
video reference material
problem link: