Tutorialspoint.dev

Delete middle element of a stack

Given a stack with push(), pop(), empty() operations, delete middle 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 idea is to use recursive calls. We first remove all items one by one, then we recur. After recursive calls, we push all items back except the middle item.

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(stack<char> &st, int n,
                          int curr=0)
{
   // If stack is empty or all items
   // are traversed
   if (st.empty() || curr == n)
     return;
  
   // Remove current item
   int x = st.top();
   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
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)

/div>

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)


Output:

7 6 5 3 2 1


This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter