Skip to content

02.ImplementQueueUsingStacks.md

Latest commit

 

History

History
282 lines (202 loc) · 6.84 KB

02.ImplementQueueUsingStacks.md

File metadata and controls

282 lines (202 loc) · 6.84 KB

🧱 Implement Queue using Stacks (MyQueue) #232

🧩 Problem Statement

Implement a First-In-First-Out (FIFO) queue using two Last-In-First-Out (LIFO) stacks.

Your queue should support the following operations:

  • push(x) — Insert an element into the queue.
  • pop() — Remove the element from the front of the queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

You must use only standard stack operations: push, pop, top, size, and empty.

💡 Intuition

Stacks follow LIFO (Last In, First Out) order, while queues follow FIFO (First In, First Out). To implement a queue using stacks, we must reverse the order of elements when needed so that the oldest element can be accessed first.

Imagine pushing elements into one stack, then reversing them into another stack to mimic queue behavior.

⚙️ Approach — Using Two Stacks (Costly Push)

We use two stacks:

  • s1: The main stack that always keeps elements in queue order (front at top).
  • s2: The helper stack used temporarily during the push operation.

🧠 How It Works

When we push(x):

  1. Move all elements from s1 → s2.
  2. Push x into s2 (new element goes at the bottom of the queue).
  3. Move everything back from s2 → s1.

Now s1.top() is always the front of the queue.

✅ Operations Breakdown

1. push(x) — O(n)

Rearrange elements to maintain queue order.

void push(int x) {
    while (s1.size()) {
        s2.push(s1.top());
        s1.pop();
    }
    s2.push(x);
    while (s2.size()) {
        s1.push(s2.top());
        s2.pop();
    }
}

2. pop() — O(1)

Simply pop from s1 (front element).

int pop() {
    int top = s1.top();
    s1.pop();
    return top;
}

3. peek() — O(1)

Return the element at the front.

int peek() {
    return s1.top();
}

4. empty() — O(1)

Check if the queue is empty.

bool empty() {
    return s1.empty();
}

🧩 Full Code

class MyQueue {
private:
    stack<int> s1, s2;

public:
    MyQueue() { }
    
    void push(int x) {
        while (s1.size()) {
            s2.push(s1.top());
            s1.pop();
        }
        s2.push(x);
        while (s2.size()) {
            s1.push(s2.top());
            s2.pop();
        }
    }
    
    int pop() {
        int top = s1.top();
        s1.pop();
        return top;
    }
    
    int peek() {
        return s1.top();
    }
    
    bool empty() {
        return s1.empty();
    }
};

🧪 Example Walkthrough

Example:

MyQueue q;
q.push(1);
q.push(2);
q.push(3);
cout << q.peek(); // 1
cout << q.pop();  // 1
cout << q.peek(); // 2

Step-by-Step Visualization:

Operation s1 (top → bottom) s2 (top → bottom) Output
push(1) 1 -
push(2) 1, 2 -
push(3) 1, 2, 3 -
peek() 1, 2, 3 - 1
pop() 2, 3 - 1
peek() 2, 3 - 2

⏱️ Complexity Analysis

Operation Time Complexity Space Complexity Explanation
push() O(n) O(n) Transfers all elements twice
pop() O(1) O(1) Just one stack pop
peek() O(1) O(1) Top element access
empty() O(1) O(1) Empty check

⚡ Alternate (Optimized) Approach — Costly Pop

Instead of making push costly, we can make pop costly and keep push O(1). This is often the preferred method in interviews and practice.

Idea:

  • Push directly to s1.
  • When popping, move elements to s2 only when s2 is empty.
class MyQueue {
private:
    stack<int> s1, s2;
public:
    void push(int x) {
        s1.push(x);
    }

    int pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int val = s2.top();
        s2.pop();
        return val;
    }

    int peek() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};

⏱️ Optimized Complexity

Operation Time Complexity Explanation
push() O(1) Direct push to stack
pop() Amortized O(1) Moves elements only when needed
peek() Amortized O(1) Similar logic as pop
empty() O(1) Constant check

🧠 Tips & Tricks

  • 🌀 Trade-off: You can choose to make either push() or pop() costly.
  • 🧮 Amortized Complexity: In the optimized version, every element moves at most once between stacks, so operations average O(1).
  • ⚙️ In interviews: Be ready to explain both approaches and their trade-offs.
  • 💡 Use built-in stack<int> from STL for simplicity.

🧪 Test Cases

MyQueue q;
q.push(10);
q.push(20);
q.push(30);

cout << q.peek() << endl;  // 10
cout << q.pop() << endl;   // 10
cout << q.peek() << endl;  // 20
cout << (q.empty() ? "Yes" : "No") << endl; // No

q.pop();
q.pop();
cout << (q.empty() ? "Yes" : "No") << endl; // Yes

❓ FAQs

Q1. Why do we need two stacks? Because one stack alone can’t reverse order; the second stack helps reverse element order to mimic FIFO behavior.

Q2. Which approach is better? The optimized (costly pop) version — it gives amortized O(1) per operation and is preferred in real-world and interviews.

Q3. Can we implement this using recursion instead of two stacks? Yes — theoretically by using the call stack, but it’s inefficient and not recommended in practice.

Q4. Why use STL stack<int>? It provides constant time push, pop, top, and empty operations — perfect for this problem.

🧭 Summary

Method push pop peek empty Best For
Costly Push O(n) O(1) O(1) O(1) Simple logic
Costly Pop (Optimized) O(1) Amortized O(1) Amortized O(1) O(1) Interview use