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.