Delete middle element of a stack

Difficulty Level Easy
Frequently asked in Amazon
Recursion StackViews 5487

Problem Statement

Given a data structure (stack). Write a program to delete the middle element of the given stack using the basic functions of the stack –

  • push() – to insert an element in the stack.
  • pop() – to remove/delete the top element from the stack.
  • empty() – to check if the size of the stack is greater than 0 or not.

Print the updated stack i.e. the stack after the deletion of the element in the middle. The use of any other data structure is not allowed.

Delete middle element of a stack

Example

1 2 3 4 5
1 2 4 5
10 20 30 40 50 60
10 20 40 50 60

Algorithm

  1. Initialize a stack data structure and push the elements in it.
  2. Create a function deleteMiddle that accepts the stack, it’s size and a variable to represent the current index as it’s parameters. Set the default value of the current index variable as 0.
  3. Check if the stack is empty or the current index variable is equal to the size of the stack, return.
  4. Create a variable x and store the top of the stack in it. Remove/delete the element at the top of the stack.
  5. Make the recursive call to the function itself with the stack, size of the stack and value of the current index variable+1 as it’s parameters.
  6. Check if the value of the current index variable is not equal to the half of the size of stack i.e. if the value of the current index variable is not equal to the middle index of the stack, push the variable x back in the stack.
  7. After that, traverse while the size of the stack is not equal to 0. Create a variable p and store the top of the stack in it, pop the top of the stack and print the variable p for all the iterations.

This works because we are taking the help of recursion to keep the top of the stack which we have stored in variable x to keep stored. We keep on removing the elements from the original stack and keep on storing inside variable x which here acts as a temporary stack. And we re-insert the all the elements into the original stack except the element for which value of current = n/2.

Code

C++ Program to delete middle element of a stack

#include<iostream>
#include<stack> 
using namespace std; 

void deleteMiddle(stack<char> &s, int n, int current=0){ 
    if(s.empty() || current == n){ 
        return; 
    }
    int x = s.top(); 
    s.pop();
    
    deleteMiddle(s, n, current+1); 
    
    if(current != n/2){ 
        s.push(x); 
    }
}

int main(){ 
    stack<char> st; 
    
    st.push('5'); 
    st.push('4'); 
    st.push('3'); 
    st.push('2'); 
    st.push('1'); 
    
    deleteMiddle(st, st.size()); 
    
    while(!st.empty()){ 
        char p=st.top(); 
        st.pop(); 
        cout << p << " "; 
    } 
    
    return 0; 
}
1 2 4 5

Java Program to delete middle element of a stack

import java.io.*; 
import java.util.*; 
  
class delMiddle{ 
  
    static void deleteMiddle(Stack<Character> st, int n, int curr){ 
          
        if(st.empty() || curr == n){ 
            return; 
        }
          
        char x = st.pop(); 
          
        deleteMiddle(st, n, curr+1); 
          
        if(curr != n/2){ 
            st.push(x); 
        }
    } 
      
    public static void main(String args[]){
        
        Stack<Character> st = new Stack<Character>(); 
      
        st.push('5'); 
        st.push('4'); 
        st.push('3'); 
        st.push('2'); 
        st.push('1'); 
        
        deleteMiddle(st, st.size(), 0); 
      
        while(!st.empty()){ 
            char p=st.pop(); 
            System.out.print(p + " "); 
        } 
    } 
}
1 2 4 5

Complexity Analysis

Time Complexity

O(N) where n is the number of elements in stack. Because we have removed all elements from the stack and then re-inserted them into the stack. The insertionand removal of an element from the stack takes O(1) time. Thus the time complexity for the algorithm is linear.

Space Complexity

O(N) because we are using recursion which will use space for storing the removed elements.

Translate »