### 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

- Create an empty temporary stack temp.
- Pop N/2 elements from the given stack and Push it into the temp stack.
- Pop top of the given stack , this is the targeted middle element .
- Pop all elements from the temp stack and Push it into the given stack .
- 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

- Create a recursive function which will accept the current stack and initial size of the input stack .
- 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
- 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.
- Once the recursive call completes , push x into the stack .
- 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.