Stack: Delete the middle element from the stack.

Problem Statement:

You are given a stack, you need to delete the middle element from it.
You should delete the middle element without using any other data structure.

Example

Input : Stack[] = [1, 2, 3, 4, 5]
Output : Stack[] = [1, 2, 4, 5]

Solution

This can be done with the help of recursion.
So during recursion, we remove the elements one by one.
Then when we reach end of the stack, we insert the removed elements.
While inserting the elements, we check if the element is a middle element, if it is the middle element, then we dont add it.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

void delete_middle_element(stack<char> &st, int n, int curr=0)
{
   // base case if the stack is empty or all the items are traversed.
   if (st.empty() || curr == n)
     return;
 
   // remove the current element
   char x = st.top();
   st.pop();
 
   // start removing the next elements
   delete_middle_element(st, n, curr+1);
 
   // push all the elements into the stack,
   // without adding the middle element.
   if (curr != n/2)
     st.push(x);
}
 
int main()
{
    stack<char> st;
 
    //push elements into the stack
    st.push('1');
    st.push('2');
    st.push('3');
    st.push('4');
    st.push('5');
    st.push('6');
    st.push('7');
 
    delete_middle_element(st, st.size());
 
    //print the result
    while (!st.empty())
    {
        char p=st.top();
        st.pop();
        cout << p << " ";
    }
    return 0;
}

Output:

Result = 7 6 5 3 2 1