stack me operation

C++ Code

#include <stack>
using namespace std;

void insert(stack<int>& st, int x){
    if(st.empty() || st.top() <= x){
        st.push(x);
        return;
    }

    int temp = st.top();
    st.pop();

    insert(st, x);

    st.push(temp);
}

void sortStack(stack<int>& st){
    if(st.empty()) return;

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

    sortStack(st);

    insert(st, x);
}

---

Idea in Simple Words

1. Remove the top element.
2. Sort the remaining stack recursively.
3. Insert the removed element in the correct position.

---

Example

Initial stack (top → bottom)

3
1
4
2

Sorted stack

4
3
2
1

(bottom → top → 1 2 3 4)

---

Complexity

• Time: O(n²)
• Space: O(n) recursion stack

1. Reverse a Stack using Recursion

Idea

1. Pop the top element.
2. Reverse the remaining stack.
3. Insert the popped element at the bottom.

Code (C++)

#include <stack>
using namespace std;

void insertBottom(stack<int>& st, int x){
    if(st.empty()){
        st.push(x);
        return;
    }

    int temp = st.top();
    st.pop();

    insertBottom(st, x);

    st.push(temp);
}

void reverseStack(stack<int>& st){
    if(st.empty()) return;

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

    reverseStack(st);

    insertBottom(st, x);
}

---

2. Delete Middle Element of Stack

Idea

1. Find the middle index k = size/2.
2. Recursively pop elements.
3. Skip pushing the middle element back.

Code

#include <stack>
using namespace std;

void solve(stack<int>& st, int k){
    if(k == 1){
        st.pop();
        return;
    }

    int temp = st.top();
    st.pop();

    solve(st, k-1);

    st.push(temp);
}

void deleteMiddle(stack<int>& st){
    int k = st.size()/2 + 1;
    solve(st, k);
}

---

3. Sort a Stack using Recursion

Idea

1. Pop element.
2. Sort remaining stack.
3. Insert element in sorted position.

void insert(stack<int>& st, int x){
    if(st.empty() || st.top() <= x){
        st.push(x);
        return;
    }

    int temp = st.top();
    st.pop();

    insert(st, x);

    st.push(temp);
}

void sortStack(stack<int>& st){
    if(st.empty()) return;

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

    sortStack(st);

    insert(st, x);
}

---

Key Pattern (Important for Interviews)

All these follow the same recursion template:

1 Remove element
2 Solve smaller problem recursively
3 Insert element back correctly