Data Modelling & AI Data Structure & Algorithm

Delete middle element of a stack

31 July 2024

2

Given a stack with push(), pop(), and empty() operations, The task is to delete the middle element of it without using any additional data structure.

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]

The Easy And Brute Force Way To do it:

The Approach:

we have the stack we just put all the element of stack into a vector then traverse over the vector and put the print the element/push into stack ignoring the mid element for even (n/2) and for odd (ceil(n/2)).

C++

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
 
int main() {
    stack<char> st;
    st.push('1');
    st.push('2');
    st.push('3');
    st.push('4');
    st.push('5');
    st.push('6');
    st.push('7');
    vector<char>v;
    while(!st.empty()){
      v.push_back(st.top());
      st.pop();
    }
    int n=v.size();
    if(n%2==0){
      int target=(n/2);
      for(int i=0;i<n;i++){
        if(i==target)continue;
        st.push(v[i]);
      }
    }else{
      int target=ceil(n/2); 
      for(int i=0;i<n;i++){
        if(i==target)continue;
        st.push(v[i]);
      }
    }
    cout<<"Printing stack after deletion of middle: "; 
    while (!st.empty()) {
        char p = st.top();
        st.pop();
        cout << p << " ";
    }
    return 0;
}

Java

import java.util.Stack;
import java.util.Vector;
 
public class Main {
 
    public static void main(String[] args) {
        Stack<Character> st = new Stack<Character>();
        st.push('1');
        st.push('2');
        st.push('3');
        st.push('4');
        st.push('5');
        st.push('6');
        st.push('7');
        Vector<Character> v = new Vector<Character>();
        while (!st.empty()) {
            v.add(st.pop());
        }
        int n = v.size();
        if (n % 2 == 0) {
            int target = (n / 2);
            for (int i = 0; i < n; i++) {
                if (i == target) continue;
                st.push(v.get(i));
            }
        } else {
            int target = (int) Math.ceil(n / 2);
            for (int i = 0; i < n; i++) {
                if (i == target) continue;
                st.push(v.get(i));
            }
        }
        System.out.print("Printing stack after deletion of middle: ");
        while (!st.empty()) {
            char p = st.pop();
            System.out.print(p + " ");
        }
    }
}

Python3

import math 
 
st = []
st.append('1')
st.append('2')
st.append('3')
st.append('4')
st.append('5')
st.append('6')
st.append('7')
 
v = []
 
while(len(st) > 0):
    v.append(st[0])
    del st[0]
     
n = len(v)
 
if n%2==0:
    target = math.floor(n/2)
    for i in range(0, n):
        if i==target:
            continue
        st.append(v[i])
else:
    target = math.floor(n/2) 
    for i in range(0, n):
        if i==target:
            continue
        st.append(v[i])
 
print("Printing stack after deletion of middle:", end = " ")
 
while (len(st) > 0):
    p = st[0]
    del st[0]
    print(p, end = " ")
     
# The code is contributed by Gautam goel. 

C#

// C# code to delete middle of a stack
using System;
using System.Collections.Generic;
  
class GFG {
    public static void Main(){
        Stack<char> st = new Stack<char>();
  
        // push elements into the stack
        st.Push('1');
        st.Push('2');
        st.Push('3');
        st.Push('4');
        st.Push('5');
        st.Push('6');
        st.Push('7');
      
        List<char> v = new List<char>();
        while(st.Count != 0){
            v.Add(st.Peek());
            st.Pop();
        }
        int n = v.Count;
        int target = (n/2);
        for(int i = 0; i<n; i++){
            if(i == target) continue;
            st.Push(v[i]);
        }
        Console.WriteLine("Printing stack after deletion of middle : ");
        while(st.Count != 0){
            char p = st.Peek();
            st.Pop();
            Console.Write(p + " ");
        }
    }
}
// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)

Javascript

let st = [];
st.push('1');
st.push('2');
st.push('3');
st.push('4');
st.push('5');
st.push('6');
st.push('7');
 
let v = [];
 
while(st.length > 0){
    v.push(st[0]);
    st.shift();
}
     
let n = v.length;
 
if(n%2==0){
    let target = Math.floor(n/2);
    for(let i = 0; i < n; i++){
        if(i==target){
            continue;
        }
       st.push(v[i]);
    }
}
else{
    let target = Math.floor(n/2);
    for(let i = 0; i < n; i++){
        if(i==target){
            continue;
        }    
        st.push(v[i]);
    }
}
 
console.log("Printing stack after deletion of middle: ");
 
while (st.length > 0){
    let p = st[0];
    st.shift();
    console.log(p + " ");
}
     
// The code is contributed by Nidhi goel.

Output

Printing stack after deletion of middle: 1 2 3 5 6 7

Time Complexity: O(N), For the Traversing.
Auxiliary Space: O(N), For the Vector.

Delete the middle element of a stack using recursion:

Below is the idea to solve the problem

Remove elements of the stack recursively until the count of removed elements becomes half the initial size of the stack, now the top element is the middle element thus pop it and push the previously removed elements in the reverse order.

Follow the steps below to implement the idea:

Store the stack size in a variable sizeofstack and a variable current to track the current size of stack.
Recursively pop out the elements of the stack
- Pop the element from the stack and increment current by one then recur for the remaining stack.
- The base case would be when the current becomes equal to sizeofstack / 2 then pop the top element.
- Push the element that was popped before the recursive call.

Below is the Implementation of the above approach:

C++

// C++ code to delete middle of a stack
// without using additional data structure.
#include<bits/stdc++.h>
using namespace std;
 
// Deletes middle of stack of size
// n. Curr is current item number
    void deleteMid_util(stack<char>&s, int sizeOfStack, int current)
    {
        //if current pointer is half of the size of stack then we 
        //are accessing the middle element of stack.
        if(current==sizeOfStack/2)
        {
            s.pop();
            return;
        }
         
        //storing the top element in a variable and popping it.
        int x = s.top();
        s.pop();
        current+=1;
 
        //calling the function recursively.
        deleteMid_util(s,sizeOfStack,current);
         
        //pushing the elements (except middle element) back 
        //into stack after recursion calls.
        s.push(x);
    }
    void deleteMid(stack<char>&s, int sizeOfStack)
    {
        deleteMid_util(s,sizeOfStack,0);
    }
 
//Driver function to test above functions
int main()
{
    stack<char> st;
 
    //push elements into the stack
    st.push('1');
    st.push('2');
    st.push('3');
    st.push('4');
    st.push('5');
    st.push('6');
    st.push('7');
 
    deleteMid(st, st.size());
 
    // Printing stack after deletion
    // of middle.
    while (!st.empty())
    {
        char p=st.top();
        st.pop();
        cout << p << " ";
    }
    return 0;
}

Java

// Java code to delete middle of a stack
// without using additional data structure.
import java.io.*;
import java.util.*;
 
public class GFG {
 
    // Deletes middle of stack of size
    // n. Curr is current item number
    static void deleteMid(Stack<Character> st,
                              int n, int curr)
    {
         
        // If stack is empty or all items
        // are traversed
        if (st.empty() || curr == n)
            return;
         
        // Remove current item
        char x = st.pop();
         
        // Remove other items
        deleteMid(st, n, curr+1);
         
        // Put all items back except middle
        if (curr != n/2)
            st.push(x);
    }
     
    // Driver function to test above functions
    public static void main(String args[]) 
    {
        Stack<Character> st =
                  new Stack<Character>();
     
        // push elements into the stack
        st.push('1');
        st.push('2');
        st.push('3');
        st.push('4');
        st.push('5');
        st.push('6');
        st.push('7');
     
        deleteMid(st, st.size(), 0);
     
        // Printing stack after deletion
        // of middle.
        while (!st.empty())
        {
            char p=st.pop();
            System.out.print(p + " ");
        }
    }
}
 
// This code is contributed by 
// Manish Shaw (manishshaw1)

Python3

# Python3 code to delete middle of a stack
# without using additional data structure.
  
# Deletes middle of stack of size
# n. Curr is current item number
class Stack:
    def __init__(self):
        self.items = []
      
    def isEmpty(self):
        return self.items == []
      
    def push(self, item):
        self.items.append(item)
      
    def pop(self):
        return self.items.pop()
      
    def peek(self):
        return self.items[len(self.items)-1]
      
    def size(self):
        return len(self.items) 
          
def deleteMid(st, n, curr) :
 
    # If stack is empty or all items
    # are traversed
    if (st.isEmpty() or curr == n) :
        return
      
    # Remove current item
    x = st.peek()
    st.pop()
      
    # Remove other items
    deleteMid(st, n, curr+1)
      
    # Put all items back except middle
    if (curr != int(n/2)) :
        st.push(x)
  
# Driver function to test above functions
st = Stack()
  
# push elements into the stack
st.push('1')
st.push('2')
st.push('3')
st.push('4')
st.push('5')
st.push('6')
st.push('7')
  
deleteMid(st, st.size(), 0)
  
# Printing stack after deletion
# of middle.
while (st.isEmpty() == False) :
    p = st.peek()
    st.pop()
    print (str(p) + " ", end="")
 
# This code is contributed by
# Manish Shaw (manishshaw1)

C#

// C# code to delete middle of a stack
// without using additional data structure.
using System;
using System.Collections.Generic;
 
class GFG {
     
    // Deletes middle of stack of size
    // n. Curr is current item number
    static void deleteMid(Stack<char> st, 
                          int n, 
                          int curr = 0)
    {
         
        // If stack is empty or all 
        // items are traversed
        if (st.Count == 0 || curr == n)
            return;
         
        // Remove current item
        char x = st.Peek();
        st.Pop();
         
        // Remove other items
        deleteMid(st, n, curr+1);
         
        // Put all items 
        // back except middle
        if (curr != n / 2)
            st.Push(x);
    }
     
    // Driver Code
    public static void Main() 
    {
        Stack<char> st = new Stack<char>();
 
        // push elements into the stack
        st.Push('1');
        st.Push('2');
        st.Push('3');
        st.Push('4');
        st.Push('5');
        st.Push('6');
        st.Push('7');
     
        deleteMid(st, st.Count);
     
        // Printing stack after 
        // deletion of middle.
        while (st.Count != 0)
        {
            char p=st.Peek();
            st.Pop();
            Console.Write(p + " ");
        }
    }
}
 
// This code is contributed by
// Manish Shaw (manishshaw1)

Javascript

<script>
    // Javascript code to delete middle of a stack
    // without using additional data structure.
     
    // Deletes middle of stack of size
    // n. Curr is current item number
    function deleteMid(st, n, curr)
    {
          
        // If stack is empty or all items
        // are traversed
        if (st.length == 0 || curr == n)
            return;
          
        // Remove current item
        let x = st[st.length - 1];
        st.pop();
          
        // Remove other items
        deleteMid(st, n, curr+1);
          
        // Put all items back except middle
        if (curr != parseInt(n/2, 10))
            st.push(x);
    }
     
    let st = [];
      
    // push elements into the stack
    st.push('1');
    st.push('2');
    st.push('3');
    st.push('4');
    st.push('5');
    st.push('6');
    st.push('7');
 
    deleteMid(st, st.length, 0);
 
    // Printing stack after deletion
    // of middle.
    while (st.length > 0)
    {
      let p = st[st.length - 1];
      st.pop();
      document.write(p + " ");
    }
     
    // This code is contributed by suresh07.
</script>

Output

7 6 5 3 2 1

Time Complexity: O(N), For the recursive calls
Auxiliary Space: O(N), For the Recursion call Stack