Delete Middle Element of a Stack

Hello geeks, In this tutorial, we would be learning how to delete middle element of a stack. Firstly we would be looking into the problem statement, different approaches to solve the problem, time complexity and space complexity of the different approaches.

Problem statement

Given a stack with push(), pop(), and empty() operations, delete the middle of the stack. Middle: ceil((size_of_stack+1)/2) (1-based index)

Input  : Stack[] = [1, 2, 3, 4, 5]
Output : Stack[] = [1, 2, 4, 5]
Input  : Stack[]  = [1, 2, 3, 4, 5, 6]
Output : Stack[] = [1, 2, 4, 5, 6]

Explanation

As we can clearly see we are asked to delete the middle element of the stack. A stack is a data structure in which each new element is pushed onto the top of the stack. It supports the push() operation which helps to push elements onto the stack, a pop() function which removes elements from the top of the stack and the empty function tells us whether the stack is empty or not.

How to Approach?

There are different ways to solve this problem, we would be looking into recursive and iterative approaches to solve the problem. Also, we would be using stl stack for both approaches. STL stnds for standard template library help us with the common data structures and their functions.

1) Recursive approach

The recursive approach is very easy to comprehend. We would be using basic recursion to pop elements out of the stack and then store them back except for the middle element. To do this we will maintain a count variable to keep track of the number of elements we popped.

Once the value of the count reaches half the size of the stack we will get the middle element. Now we will pop the element and in the return calls, all our previous elements will get stored back into the stack. So basically this approach is using recursive calls to pop the elements of the stack and then store back the elements except for the middle element.

Delete Middle Element of a Stack C++ Code

#include<bits/stdc++.h>
using namespace std;
//Recursive function to remove middle item of the stack
void solve(stack<int>&s,int &count,int size){
    if(count==size){
        s.pop();
        return;
    }
    //top function is used to return the element at top of stack
    int x=s.top(); //stores top element of the stack
    s.pop();
    count=count+1;
    solve(s,count,size);
    s.push(x);
    return;
}
int main()
{
    stack<int>s;
    //code to insert element in stack
    for(int i=1;i<=6;i++){
        s.push(i);
    }
    int count=0;
    
    //function call
    solve(s,count,s.size()/2);
    //code to display elements of the stack
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
}

Delete Middle Element of a Stack Java Code

import java.util.Stack;
class cwg{
    //function to remove middle element of stack
    static void solve(Stack<Integer>s,int count, int size){
        if(count==size){
            s.pop();
            return;
        }
        int x=s.pop();
        count=count+1;
        solve(s,count,size);
        s.push(x);
    }
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        //code to push elements in stack
        for(int i = 1; i <= 6; i++){
            stack.push(i);
        }
        int count=0;
        //function call
        solve(stack,count,stack.size()/2);
        //code to print stack elements
        while(!stack.empty()){
            System.out.print(stack.pop()+" ");
        }
    }
}

Time Complexity: The time complexity for the above approach is O(n).

Space Complexity: The space complexity for the above approach is O(n).

2) Iterative Approach

If we keep in our minds that recursion uses stack then we can also think about an iterative approach to solve the problem. We would be requiring an additional data structure (stack here) to store the elements before the middle element and after we pop the middle element we would again store back our elements back into the original stack.

Delete Middle Element In Stack C++ Code :

Delete Middle Element In Stack Java Code :

import java.util.Stack;


public class cwg2 {


    //function to remove middle element of stack
    static void solve(Stack<Integer>s,int size){
    int count=0;
    Stack<Integer>temp=new Stack<Integer>();//temp stack to store elements


    ////remove all elements before the middle element and store them in other stack
    while(count<size){
        temp.push(s.pop());
        count++;
    }
    s.pop();
    
    //store the other popped elements back into the original stack
    while(!temp.isEmpty()){
        s.push(temp.pop());
    }
}
    public static void main(String args[]) {
        Stack<Integer> s = new Stack<Integer>();


        //code to push elements into stack
        for(int i = 0; i < 10; i++) {
            s.push(i);
        }


        //function call
        solve(s, s.size() / 2);


        //code to display elements of stack
        while(!s.isEmpty()) {
            System.out.println(s.pop());
        }
    }
}

Time Complexity: The time complexity of the above approach is O(n).

Space Complexity: The space complexity of the above approach is O(n).

Frequently Asked Questions

 How do I remove a middle element from a stack?

Ans : To remove the middle element of the stack we can use recursion or iteration as explained in the above article.

2)How do I remove a specific element from a stack?

Ans: To remove a specific element from stack we can pop all the previous elements before the required element and push back all the elements except for the required element, using a similar recursive approach or iterative approach.

Conclusion

In this tutorial, we learned how to remove the middle element of the stack through different approaches. We also looked into the time and space complexity of the approaches.