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.