Stack: Delete middle element of a stack

Given a stack, you need to delete the middle element.

You should not use any additional data structure.

Input: [1, 2, 3, 4, 5]

Output [5, 4, 2, 1]

In this approach, insert all the elements of the stack into a vector.

Then push the elements into the stack, by skipping the mid element, for even (n/2) and for odd (ceil(n/2))

Time Complexity: O(n)

Space Complexity: O(n)

Take a temp stack.

Run the loop, till the count half of the initial size.

Pop the element from the stack, push in temp.

Pop the top element from the stack.

Then put rest of the element from the original stack to temp stack, then again push them back.

Time Complexity: O(1)

Space Complexity: O(1)

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

void solution_1(stack<int>& st, int size) 
{
    vector<int> v;
    while(!st.empty()) 
    {
        v.push_back(st.top());
        st.pop();
    }

    int mid = size / 2;

    v.erase(v.begin() + mid);

    for(int i = v.size() - 1; i >= 0; i--) 
    {
        st.push(v[i]);
    }
}

void solution_2(stack<int>& st)
{
    int n = st.size();
    stack<int> tempSt;
    int count = 0;

    while (count < n / 2) 
    {
        int c = st.top();
        st.pop();
        tempSt.push(c);
        count++;
    }

    st.pop();

    while (!tempSt.empty()) 
    {
        st.push(tempSt.top());
        tempSt.pop();
    }
}


int main() 
{
    stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);
    st.push(50);

    int size = st.size();

    solution_1(st, size);

    while (!st.empty()) 
    {
        int p = st.top();
        st.pop();
        cout << p << " ";
    }
    
    return 0;
}

Output

50 40 20 10