Implement Stack Using Queues (2 Approaches) | LeetCode 225 Explained with C++

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!

Introduction

Before we jump into the code, let's briefly review the two main characters of our story:

1. Stack: A stack is a collection of elements that follows the LIFO (Last In, First Out) principle. Think of a stack of plates in a cafeteria. The last plate you put on the top is the first one you pick up.
2. Queue: A queue follows the FIFO (First In, First Out) principle. Think of a line of people waiting to buy movie tickets. The first person to join the line is the first person to get a ticket.

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.

Problem Statement

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 only push to back, peek/pop from front, size, and is empty operations are allowed.

Approach 1: Brute Force (Using Two Queues)

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.

Intuition

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.

Algorithm

Push Operation (push(x)):

1. Add the new element x to the empty helper queue, q2.
2. One by one, remove all elements from the main queue q1 and push them into q2.
3. Swap the queues 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.

C++ Implementation

#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();
    }
};

Complexity analysis

Advantages:

• Easy to understand and visualize.
• pop() and top() operations are blazing fast (O(1)).

Disadvantages:

• Uses two queues, which wastes slightly more memory overhead.
• The push operation is slow (O(n)) because of the constant data transfer between q1 and q2.

Approach 2: Better / Optimal (Using One Queue)

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.

Intuition

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 $n-1$ times (where $n$ is the new size of the queue), our newest element rotates its way to the front!

Algorithm

Push Operation (push(x)):

1. Get the current size of the queue and store it in a variable size. (This represents the $n-1$ elements currently in the queue).
2. Push the new element x into the queue.
3. Run a loop size times:
   • Extract the front element of the queue.
   • Push it to the back of the queue.
   • Pop it from the front.

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.

Visualization

Let's visualize the rotation for push(3) when the queue already has [2, 1].

c++ implementation

#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();
    }
};

Dry Run

Complexity Analysis

advantages:

• Uses strictly one queue, making the code cleaner and reducing memory overhead.
• Demonstrates a deeper understanding of data structure manipulation (rotation).

Disadvantages:

• push is still O(n).

Comparison Table

Here is a quick snapshot summarizing both approaches.

Why Queue Rotation Works

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).

1. Add D to the back:Front -> [A, B, C, D] <- Back
2. Move A to the back:Front -> [B, C, D, A] <- Back
3. Move B to the back:Front -> [C, D, A, B] <- Back
4. Move C to the back:Front -> [D, A, B, C] <- Back

By rotating exactly $n-1$ times (where $n$ 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!

Edge Cases

A high-quality interview answer always considers edge cases. Here are a few to keep in mind:

• Empty Stack: What happens if 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");.
• Single Element Stack: If the stack has only one element, 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.
• Continuous Pushes/Pops: The structural integrity of the queue must hold regardless of the sequence of operations. Because we fully rotate the queue on every single push, the stack order is permanently baked into the queue. It will survive any combination of pushes and pops.

Common Mistakes

When coding this under the pressure of a whiteboard interview, candidates often make the following errors:

1. Forgetting to capture the size before pushing: If you write 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!
2. Off-by-one errors: Using <= size instead of < size in the for loop causes the same problem as above.
3. Incorrect queue swapping (Two Queues Approach): Forgetting to swap q1 and q2 at the end of the push operation leaves your elements stranded in the helper queue.
4. Popping from an empty queue: Failing to consider what happens if a user calls pop() on a newly instantiated MyStack.

Interview Tips

💡 Pro-Tip: Never jump straight to the single-queue optimal solution unless you are running out of time.

1. Start with the Brute Force: Interviewers love seeing a progression of thought. Start by explaining the two-queue approach verbally. Mention the time and space complexities.
2. Pivot to the Optimization: Once the interviewer nods, say, "While this works perfectly, we are using an extra queue. I can optimize the space overhead by using a single queue and applying queue rotation." This shows strong communication and problem-solving skills.
3. Discuss Complexities clearly: Don't just throw out "O(N)". Explain why it is O(N). Explain that transferring elements between queues or rotating the queue requires iterating over all existing elements.
4. Follow-up Question: The interviewer might ask: "Can we make push O(1) and pop O(N)?"Yes! You can choose to optimize 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 $n-1$ times right before popping, making pop O(N). Which one is better depends on the system’s read/write ratio.

FAQs

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:

problem link:

https://leetcode.com/problems/implement-stack-using-queues/