# Delete Middle Element of the Stack ### Problem statement

Given a stack of integers , delete the middle element of the stack using only standard stack operations like push , pop , size , empty . If the size of the stack is even then delete the lower element .

NOTE : You can also not use any other data structure .

Sample example : In the first example , the size of the stack is odd and 3 is the middle element , we will delete it .
In the second example , the size of the stack is even , 3 and 4 both are the middle element . 4 is lower in the stack so we will delete that .

In this article we will try to understand different ways to delete the middle element of the stack .
Approach
If the stack has N elements , then we need to somehow store N/2 elements of the stack and then delete (N/2 + 1)-th element of the stack . Then we can push the top N/2 elements that we have stored . To store N/2 elements we have two methods: either we can go for an interactive approach and use a temporary stack or we can go for a recursive approach and use a recursive stack . Let’s try to understand both .

### Algorithm for Iterative approach

1. Create an empty temporary stack temp.
2. Pop N/2 elements from the given stack and Push it into the temp stack.
3. Pop top of the given stack , this is the targeted middle element .
4. Pop all elements from the temp stack and Push it into the given stack .
5. This will be the final stack after deleting the middle element .

### Dry Run of above algorithm ### C++ implementation

Time complexity : O(N)
Space complexity : O(N)

### Algorithm for Recursive Approach

1. Create a recursive function which will accept the current stack and initial size of the input stack .
2. In each call we first check if N/2 elements have already been deleted , then the top of stack will be the targeted middle element , we will pop it and stop the recursive call
3. Else we pop the top of stack and store it into a variable x , and do the recursive call for the current stack after popping.
4. Once the recursive call completes , push x into the stack .
5. The stack obtained at the end of the call is the final required stack .

### C++ implementation

```#include <bits/stdc++.h>
using namespace std;

void deleteMid(stack<int> &st ,int N){
int popped_elements = N-st.size();
if(popped_elements == (N/2)){
st.pop();
return;
}
int x=st.top();
st.pop();
deleteMid(st,N);
st.push(x);
}

void deleteMidElement(stack<int>& st)
{
int N = st.size();
deleteMid(st,N);

}

int main()
{
stack<int> st;
st.push(6);
st.push(5);
st.push(4);
st.push(3);
st.push(2);
st.push(1);

deleteMidElement(st);

while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}

return 0;
}
```

Time complexity : O(N)
Space complexity : O(N) for recursive stack

This article tried to discuss How to Delete the Middle Element of the Stack . Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.