Delete Middle Element of the Stack

Last Updated on May 11, 2023 by Prepbytes

In computer science, a stack is an abstract data type that represents a collection of elements, where the addition or removal of elements follows a Last-In-First-Out (LIFO) order. That is, the last element that was added to the stack is the first one to be removed.

To delete middle element of a stack refers to removing the element that is located in the middle of the stack. This can be a useful operation in some scenarios, such as when implementing algorithms that require removing a specific element from a stack, or when the stack contains redundant elements that need to be removed.

However, deleting the middle element of a stack can be challenging since stacks do not provide direct access to elements in the middle. Therefore, the implementation of this operation typically requires additional data structures or algorithms that traverse the stack to locate and remove the middle element.

How to Delete Middle Element of the Stack?

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 to Find Middle Element from Stack

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 to Find Middle Element from Stack

Code 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 .

Code 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

Conclusion
In conclusion, to delete middle element of a stack can be a useful operation in some scenarios, but it can also be a challenging task due to the LIFO nature of stacks and the lack of direct access to elements in the middle. The implementation of this operation typically requires additional data structures or algorithms to locate and remove the middle element, such as using two-pointers or reversing the stack temporarily. As with any data structure operation, it is important to carefully consider the time and space complexity of the implementation to ensure efficient and effective performance.

Frequently Asked Questions

Q1. Why would I want to delete the middle element of a stack?
Ans. There can be various scenarios where deleting the middle element of a stack can be useful, such as removing a specific element, removing redundant elements, or rearranging the order of elements.

Q2. Is it possible to delete the middle element of a stack without using any additional data structures or algorithms?
Ans. No, since stacks only provide access to the top element, it is not possible to directly access the middle element without traversing the stack or using additional data structures.

Q3. What is the time complexity of deleting the middle element of a stack?
Ans. The time complexity depends on the implementation and the method used to locate and remove the middle element. In the worst case, it can be O(n), where n is the number of elements in the stack.

Q4. Can deleting the middle element of a stack affect the order of the remaining elements?
Ans. Yes, deleting the middle element can change the order of the remaining elements in the stack. Therefore, it is important to consider the potential impact on the order of elements when deleting the middle element.

Q5. Is it possible to delete multiple middle elements from a stack?
Ans. Yes, it is possible to delete multiple middle elements from a stack, but it can be more complex than deleting a single middle element and may require additional algorithms or data structures.