Queue using Stack(s)

🧠 Approach 1: Using TWO Stacks (Efficient)

📌 Idea

Use:

• s1 → for push
• s2 → for pop / front

---

✅ Operations

🔹 Push (O(1))

• Push into s1

🔹 Pop / Front (Amortized O(1))

• If s2 is empty:

  • Move all elements from s1 → s2

• Then pop from s2

---

✅ Code (C++)

#include <iostream>
#include <stack>
using namespace std;

class Queue {
    stack<int> s1, s2;

public:
    void push(int x) {
        s1.push(x);
    }

    int pop() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty\n";
            return -1;
        }

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

        int val = s2.top();
        s2.pop();
        return val;
    }

    int front() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty\n";
            return -1;
        }

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

        return s2.top();
    }

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

int main() {
    Queue q;
    q.push(1);
    q.push(2);
    q.push(3);

    cout << q.front() << endl; // 1
    cout << q.pop() << endl;   // 1
    cout << q.front() << endl; // 2
}

---

⚡ Complexity

Operation	Time
push	O(1)
pop	Amortized O(1)
front	Amortized O(1)

---

🔥 Approach 2: Using ONE Stack (Recursive)

📌 Idea

• Push normally
• For pop → recursively reach bottom element

---

❗ Drawback

• Pop becomes O(n)

---

✅ Code

#include <iostream>
#include <stack>
using namespace std;

class Queue {
    stack<int> s;

public:
    void push(int x) {
        s.push(x);
    }

    int pop() {
        if (s.empty()) {
            cout << "Queue is empty\n";
            return -1;
        }

        int x = s.top();
        s.pop();

        if (s.empty()) {
            return x;
        }

        int res = pop();
        s.push(x);
        return res;
    }
};

---

🔍 Key Insight

👉 Stack = LIFO
👉 Queue = FIFO

So we reverse order twice using two stacks to simulate FIFO.

---

🎯 Interview One-Liner

“Use two stacks: one for input and one for output; transfer elements only when needed to achieve amortized O(1) operations.”