Implement Queue Using Stacks (2 Approaches) | LeetCode 232 Explained with C++

Introduction

If you are diving into the world of Data Structures and Algorithms (DSA), you have likely encountered two of the most fundamental data structures: Stacks and Queues.

To put it simply, a Queue is a linear data structure that models a real-world line of people waiting for a service. It follows the FIFO (First In, First Out) principle. The first person to join the line is the first person to be served and leave.

Conversely, a Stack follows the LIFO (Last In, First Out) principle. Think of it like a stack of plates in a cafeteria; the last plate you put on top is the first one you pick up.

Why is implementing one using the other a popular interview question? Because it forces you to think outside the box. Interviewers at top tech companies love this question because it tests your fundamental understanding of how data flows. You cannot rely on built-in queue libraries; you have to engineer a FIFO behavior using LIFO tools. It also opens the door to a deeper discussion about time complexity and amortized analysis—a favorite topic in system design and optimization.

Problem Statement

The problem is straightforward: You need to design a custom Queue data structure using only two standard Stacks.

Your custom queue must support the following standard queue operations:

• push(x): Pushes element x to the back of the queue.
• pop(): Removes the element from the front of the queue and returns it.
• peek(): Returns the element at the front of the queue without removing it.
• empty(): Returns true if the queue is empty, false otherwise.

Note: You are only allowed to use standard stack operations. This means you can only use push to top, peek/pop from top, size, and is empty.

Approach 1: Brute Force (Using Two Stacks)

When tackling an interview problem, it is perfectly fine (and often encouraged) to state the brute force solution first. It shows you can solve the problem before optimizing it.

Intuition

A stack natively gives us the newest element when we pop. But a queue requires the oldest element. If we want to get to the oldest element (which is trapped at the very bottom of the stack), we have to move all the elements sitting on top of it out of the way.

Whenever a pop or peek is needed, we can transfer all elements from our main stack to a second temporary stack. This essentially reverses their order, bringing the oldest element to the top! Once we retrieve or remove that oldest element, we must transfer all the remaining elements back to the main stack so that the original order is restored for future push operations.

Algorithm

Let's call our stacks mainStack and tempStack.

1. push(x): Simply push the element onto mainStack.
2. peek():
   • Transfer all elements from mainStack to tempStack one by one.
   • The top of tempStack is now our front queue element. Save this value.
   • Transfer everything back from tempStack to mainStack.
   • Return the saved value.
3. pop():
   • Transfer all elements from mainStack to tempStack.
   • Pop the top element from tempStack (this removes the oldest element). Save this value.
   • Transfer the remaining elements back from tempStack to mainStack.
   • Return the saved value.
4. empty(): Return true if mainStack is empty.

Dry Run

Let's execute the following operations: push(1), push(2), push(3), peek(), pop(), push(4), pop()

1. push(1)

• mainStack: [1]
• tempStack: (empty)

2. push(2)

• mainStack: [1, 2] (top is 2)
• tempStack: (empty)

3. push(3)

• mainStack: [1, 2, 3] (top is 3)
• tempStack: (empty)

4. peek()

• Transfer to temp: mainStack becomes (empty), tempStack becomes [3, 2, 1] (top is 1).
• Read top: 1.
• Transfer back: mainStack becomes [1, 2, 3], tempStack becomes (empty).

5. pop()

• Transfer to temp: mainStack becomes (empty), tempStack becomes [3, 2, 1].
• Pop top: Remove 1.
• Transfer back: mainStack becomes [2, 3], tempStack becomes (empty).

6. push(4)

• mainStack: [2, 3, 4] (top is 4)
• tempStack: (empty)

7. pop()

• Transfer to temp: mainStack becomes (empty), tempStack becomes [4, 3, 2].
• Pop top: Remove 2.
• Transfer back: mainStack becomes [3, 4], tempStack becomes (empty).

C++ Implementation

#include <stack>

class MyQueueBruteForce {
private:
    std::stack<int> mainStack;
    std::stack<int> tempStack;

public:
    MyQueueBruteForce() {}
    
    void push(int x) {
        mainStack.push(x);
    }
    
    int pop() {
        // Transfer all to tempStack
        while (!mainStack.empty()) {
            tempStack.push(mainStack.top());
            mainStack.pop();
        }
        
        // The oldest element is now at the top
        int frontElement = tempStack.top();
        tempStack.pop();
        
        // Transfer everything back to mainStack
        while (!tempStack.empty()) {
            mainStack.push(tempStack.top());
            tempStack.pop();
        }
        
        return frontElement;
    }
    
    int peek() {
        // Transfer all to tempStack
        while (!mainStack.empty()) {
            tempStack.push(mainStack.top());
            mainStack.pop();
        }
        
        // The oldest element is now at the top
        int frontElement = tempStack.top();
        
        // Transfer everything back to mainStack
        while (!tempStack.empty()) {
            mainStack.push(tempStack.top());
            tempStack.pop();
        }
        
        return frontElement;
    }
    
    bool empty() {
        return mainStack.empty();
    }
};

Complexity Analysis

Approach 2: Better / Optimal (Using Two Stacks with Lazy Transfer)

The brute force approach does a lot of redundant work. Why are we moving elements back to the main stack immediately?

Let's rethink our strategy:

• One stack (let's call it inputStack) will solely be responsible for taking in newly inserted elements.
• The second stack (outputStack) will be used solely for pop and peek operations.
• We will only transfer elements from inputStack to outputStack when outputStack is completely empty.
• Because we wait until the absolute last moment to do the heavy lifting, this is called a Lazy Transfer.

Intuition

When we pour elements from inputStack into outputStack, they are reversed. The oldest element is now perfectly sitting at the top of outputStack, ready to be popped. But here is the magic: the second oldest element is right beneath it!

We do not need to transfer the elements back. We can just leave them in outputStack. Future pop and peek operations can just read directly from outputStack in O(1) time. We only need to do another bulk transfer when outputStack eventually runs empty. Every element moves between stacks exactly once in its lifetime.

Algorithm

1. push(x): Push directly onto inputStack.
2. peek():
   • If outputStack is empty, move all elements one-by-one from inputStack to outputStack.
   • Return the top element of outputStack.
3. pop():
   • Call peek() to ensure outputStack has elements (this handles the transfer if needed).
   • Pop the top element from outputStack and return it.
4. empty():
   • Return true if both inputStack and outputStack are empty.

Visualization

Let's trace a few operations to see the lazy transfer in action.

Dry Run

Let's execute: push(1), push(2), push(3), peek(), pop(), push(4), peek(), pop(), pop()

1. push(1): inputStack = [1], outputStack = []
2. push(2): inputStack = [1, 2], outputStack = []
3. push(3): inputStack = [1, 2, 3], outputStack = []
4. peek(): outputStack is empty. Transfer inputStack to outputStack.
   • inputStack = []
   • outputStack = [3, 2, 1] (top is 1). Returns 1.
5. pop(): outputStack is NOT empty. Just pop from it!
   • Removes 1. outputStack = [3, 2] (top is 2). Returns 1.
6. push(4): Push to inputStack.
   • inputStack = [4], outputStack = [3, 2].
7. peek(): outputStack is NOT empty. Just read top.
   • Returns 2.
8. pop(): outputStack is NOT empty. Just pop from it!
   • Removes 2. outputStack = [3]. Returns 2.
9. pop(): outputStack is NOT empty. Just pop from it!
   • Removes 3. outputStack = []. inputStack = [4]. Returns 3. (Next time we pop, 4 will transfer over).

Notice how much faster this is? We only did one transfer step the entire time!

C++ Implementation

#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> inputStack;   // Stack used for enqueue (push) operations
    stack<int> outputStack;  // Stack used for dequeue (pop/peek) operations

public:
    MyQueue() {}  // Constructor initializes empty stacks
    
    // Push element x to the back of the queue
    void push(int x) {
        inputStack.push(x);  // Always push new elements onto inputStack
    }
    
    // Removes the element from the front of the queue and returns it
    int pop() {
        // Ensure outputStack has the current front element
        peek();  
        
        int frontElement = outputStack.top();  // Get the front element
        outputStack.pop();                     // Remove it from outputStack
        
        return frontElement;                   // Return the removed element
    }
    
    // Get the front element without removing it
    int peek() {
        // If outputStack is empty, transfer all elements from inputStack
        // This reverses the order so the oldest element ends up on top
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        return outputStack.top();  // The front of the queue
    }
    
    // Returns true if the queue is empty
    bool empty() {
        // Queue is empty only if BOTH stacks are empty
        return inputStack.empty() && outputStack.empty();
    }
};

Complexity Analysis

• Worst-case complexity: When outputStack is empty, pop or peek takes O(N) time because it has to move N elements from inputStack.
• Amortized complexity: Because an element is only pushed to inputStack once, moved to outputStack once, and popped once, the total time across a series of operations is proportional to the number of operations. Therefore, the average time per operation is O(1).

Why Lazy Transfer Works

Let's intuitively break down why this is so much better than brute force.

Imagine you have a stack of blocks. You want the bottom block.

Input Stack
Top
 3
 2
 1
Bottom

If you move them to another pile (the Output Stack), they reverse order:

Output Stack
Top
 1
 2
 3
Bottom

Now block 1 is on top. You take it. What is beneath it? Block 2. That is the exact next block you will need! Because the Output Stack holds the remaining elements in the perfect FIFO order, you don't need to move them back. You can just leave them there.

Any new elements arriving (like block 4 or 5) just wait patiently in the Input Stack. They don't need to be touched until the Output Stack is completely empty. This proves that every element is moved exactly once from input to output, making the heavy-lifting sparse and the overall algorithm incredibly efficient.

Complexity Comparison

To make the differences crystal clear for an interview, here is a direct comparison:

Why is the Optimal approach preferred? In software engineering, we care about the overall performance of a system over time. The brute force method causes severe lag every single time a user tries to retrieve data. The lazy transfer method guarantees that retrieval is blazing fast almost every time, with only occasional, predictable cleanup work.

Edge Cases

A flawless interview response always accounts for edge cases:

1. Empty Queue: Calling pop() or peek() on an empty queue. (In LeetCode, it is guaranteed that all calls to pop and peek are valid, but in a real-world scenario, you should throw an exception).
2. Single Element: Pushing one element and immediately popping it. The lazy transfer works seamlessly here.
3. Multiple Pushes: Pushing a massive amount of elements before a single pop. Space complexity scales linearly to O(N).
4. Consecutive Peek Operations: Calling peek() ten times in a row. The brute force would do O(N) work ten times. The optimal approach does O(N) work once, and O(1) work nine times.
5. Alternating Push and Pop: push, pop, push, pop. In this specific scenario, the optimal approach still takes O(1) time for each operation because the outputStack empties immediately, meaning only one element transfers at a time.

Common Mistakes

Watch out for these frequent pitfalls when writing this code:

1. Forgetting to transfer elements: Trying to pop from inputStack directly without moving things to outputStack will result in LIFO behavior, failing the problem.
2. Transferring on every pop: This reverts your code back to the brute force method! You must check if (outputStack.empty()) before transferring.
3. Returning the wrong stack's top: Ensure you are always returning outputStack.top(), never inputStack.top().
4. Mishandling empty queues: The empty() function must check if both stacks are empty, not just one. return inputStack.empty() && outputStack.empty();
5. Incorrect stack order after transfer: Some candidates try to use an array or queue inside to cheat. Stick strictly to standard stack API methods (push, pop, top).

Interview Tips

Why do interviewers ask this problem? It checks if you understand the conceptual difference between LIFO and FIFO. It also acts as a gateway to test your knowledge of Amortized Analysis.

• Own the Amortized Explanation: If you just say "It's O(1)", the interviewer will push back. Say: "The worst-case is O(N) when a transfer occurs. However, because every element is pushed to the input stack once, transferred to the output stack once, and popped from the output stack once, the amortized time complexity across all operations is O(1)."
• Discussing Trade-offs: Be prepared to explain why the Brute Force is terrible. Walk them through the "Consecutive Peek" edge case mentioned above.
• Why two stacks? One stack fundamentally cannot reverse the order of its own elements without a secondary holding container. You physically need two isolated environments to flip the order permanently.

FAQs

1. Can a queue be implemented using one stack? Technically yes, if you use the implicit call stack via recursion. But it still requires O(N) extra space and is essentially using "two stacks" under the hood. Standard iterative implementations require two stacks.

2. Why are two stacks needed? A single stack enforces LIFO. To get FIFO, the data order must be completely reversed. You need a second stack to hold the reversed data.

3. Why is pop() O(1) amortized? Because the costly O(N) transfer only happens when the outputStack is empty. The cost of that transfer is "paid for" by the O(1) pops that follow. Over a long sequence of operations, the average cost per operation averages out to O(1).

4. What is amortized analysis? It is a method of analyzing algorithms where the cost of an occasional expensive operation is distributed over multiple cheap operations, giving a true picture of the algorithm's average performance over time.

5. Why isn't every pop O(N)? Because we use Lazy Transfer. We leave the elements in the outputStack after the first transfer, so subsequent pops just read directly from the top in O(1) time.

6. What happens if both stacks are empty? The empty() method will return true. If you try to pop or peek, standard stack implementations will throw a runtime error (Segmentation fault in C++).

7. Is this problem actually asked in interviews? Yes, frequently. It is highly popular in screening rounds for Amazon, Microsoft, and Bloomberg.

8. Can a deque replace stacks here? A deque (Double Ended Queue) can behave like a stack, but using a deque to solve this problem defeats the purpose, as a deque is a queue. The restriction is to strictly use stack mechanics.

9. Which approach is preferred by interviewers? Approach 2 (Lazy Transfer) is the expected, optimal solution.

10. What are similar interview questions? "Implement Stack using Queues" (LeetCode 225) is the sister problem to this one. Other similar logic puzzles include the "Min Stack" problem.

Key Takeaways

• Queues are FIFO (First In, First Out) and Stacks are LIFO (Last In, First Out).
• To mimic a Queue with Stacks, we use one stack for receiving input and one stack for providing output.
• Brute Force requires moving all elements back and forth on every pop or peek, leading to O(N) time complexity for those operations.
• Lazy Transfer (Optimal Approach) delays the transfer of elements until the output stack is completely empty.
• With Lazy Transfer, every element is moved exactly once between stacks, resulting in an Amortized O(1) time complexity for all operations.
• Always ensure your empty() function checks the status of both stacks.

video reference:

code link:

https://leetcode.com/problems/implement-queue-using-stacks/description/