Delete middle element of a stack

Last Updated : 10 Feb, 2023

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

Delete middle element of a stack using another stack:

Pop the elements above the middle element of the given stack and use a temp stack to store these popped elements. Then pop the middle element and push the elements of the temp stack in the given stack.

Follow the below steps to implement the idea:

Initialize an empty stack temp and a variable count with 0.
Run a while loop till count becomes equal to half the initial size of the given stack
- Pop the element of the given stack and push them in temp.
Pop the top element from the given stack.
Run a while loop till temp becomes empty.
- Push the element of temp and push them in the given stack .

Below is the implementation of the above approach:

C++

// C++ code to delete middle of a stack with iterative method
#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 = st.size();
    stack<char> tempSt;
    int count = 0;
     
    // Put first n/2 element of st in tempSt
    while (count < n / 2) {
        char c = st.top();
        st.pop();
        tempSt.push(c);
        count++;
    }
       
    // Delete middle element
    st.pop();
       
    // Put all (n/2) element of tempSt in st
    while (!tempSt.empty()) {
        st.push(tempSt.top());
        tempSt.pop();
    }
}
 
// Driver Code
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);
 
    // 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 with iterative
// method
import java.util.Stack;
 
@SuppressWarnings("unchecked")
class Rextester 
{
   
    // Deletes middle of stack of size n. Curr is current
    // item number
    static void deleteMid(Stack<Character> st)
    {
        int n = st.size();
        Stack<Character> tempSt = new Stack();
        int count = 0;
        // put first n/2 element of st in tempSt
        while (count < n / 2) {
            char c = st.peek();
            st.pop();
            tempSt.push(c);
            count++;
        }
        // delete middle element
        st.pop();
        // put all (n/2) element of tempSt in st
        while (!tempSt.empty()) {
            st.push(tempSt.peek());
            tempSt.pop();
        }
    }
 
    // Driver function to test above functions
    public static void main(String args[])
    {
        Stack<Character> st = new 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);
 
        // Printing stack after deletion of middle.
        while (!st.empty()) {
            char p = st.peek();
            st.pop();
            System.out.print(p + " ");
        }
    }
}
 
// This code is contributed by Lovely Jain

Python3

# Python code to delete middle of a stack with iterative method
 
# Deletes middle of stack of size n. Curr is current item number
def deleteMid(st):
    n = len(st)
    tempSt = []
    count = 0
 
    # Put first n/2 element of st in tempSt
    while (count < (n / 2)-1):
        c = st[0]
        st.pop(0)
        tempSt.insert(0, c)
        count = count+1
 
    # Delete middle element
    st.pop(0)
 
    # Put all (n/2) element of tempSt in st
    while (len(tempSt) != 0):
        st.insert(0, tempSt[0])
        tempSt.pop(0)
 
 
# Driver Code
st = []
 
# insert elements into the stack
st.insert(0, 1)
st.insert(0, 2)
st.insert(0, 3)
st.insert(0, 4)
st.insert(0, 5)
st.insert(0, 6)
st.insert(0, 7)
deleteMid(st)
 
# Printing stack after deletion of middle.
while (len(st) != 0):
    p = st[0]
    st.pop(0)
    print(p, " ")
 
# This code is added by adityamaharshi21

C#

// C# code to delete middle of a stack
// without using additional data structure.
using System;
using System.Collections.Generic;
 
class GFG {
 
  static void deleteMid(Stack<char> st,int n)
  {
 
    Stack<char> tempSt = new Stack<char>();
    int count = 0;
     
    // put first n/2 element of st in tempSt
    while (count < n / 2) {
      char c = st.Peek();
      st.Pop();
      tempSt.Push(c);
      count++;
    }
     
    // delete middle element
    st.Pop();
     
    // put all (n/2) element of tempSt in st
    while (tempSt.Count != 0) {
      st.Push(tempSt.Peek());
      tempSt.Pop();
    }
 
  }
 
  // 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 utkarshshriode02.

Javascript

// JS code to delete middle of a stack with iterative method
 
// Deletes middle of stack of size n. Curr is current item number
function deleteMid(st)
{
    let n = st.length;
    let tempSt=[];
    let count = 0;
     
    // Put first n/2 element of st in tempSt
    while (count < (n / 2)-1) {
        let c = st[0];
        st.shift();
        tempSt.unshift(c);
        count++;
    }
     
    // Delete middle element
    st.shift();
     
    // Put all (n/2) element of tempSt in st
    while (tempSt.length!=0) {
        st.unshift(tempSt[0]);
        tempSt.shift();
    }
}
 
// Driver Code
    let st=[];
 
    // unshift elements into the stack
    st.unshift('1');
    st.unshift('2');
    st.unshift('3');
    st.unshift('4');
    st.unshift('5');
    st.unshift('6');
    st.unshift('7');
    deleteMid(st);
 
    // Printing stack after deletion of middle.
 
    while (st.length!=0) {
        let p = st[0];
        st.shift();
        console.log(p ," ");
    }
// This code is added by adityamaharshi21

Output

7 6 5 3 2 1

Time Complexity: O(N), For the while loop
Auxiliary Space: O(N), for temp stack space.

R

Rohit_ranjan

Improve

Previous Article

Reverse a stack without using extra space in O(n)

Check if a queue can be sorted into another queue using a stack

Similar Reads

JavaScript Program to Delete Middle Element from an Array

In this article, we will learn different approaches to how we can delete the middle element from a given array. We will use these JavaScript methods to achieve this: Methods to Delete Middle Element from an ArrayTable of Content Methods to Delete Middle Element from an ArrayUsing JavaScript Spread OperatorUsing the JavaScript splice() methodUsing t

Design a stack with operations on middle element

How to implement a stack which will support the following operations in O(1) time complexity? 1) push() which adds an element to the top of stack. 2) pop() which removes an element from top of stack. 3) findMiddle() which will return middle element of the stack. 4) deleteMiddle() which will delete the middle element. Push and pop are standard stack

Python Program To Delete Middle Of Linked List

Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5 If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it shoul

C++ Program To Delete Middle Of Linked List

Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5 If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it shoul

Java Program To Delete Middle Of Linked List

Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5 If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it shoul

Javascript Program To Delete Middle Of Linked List

Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5 If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it shoul

Delete middle of linked list

Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5 If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2-

Replace the middle element of matrix with sum of surrounding elements

Given a square matrix mat[][] of odd dimensions, the task is to change the value of the middle most element of the matrix to the sum of the elements surrounding it. Examples: Input: mat[][] = { {2, 1, 7}, {3, 7, 2}, {5, 4, 9} } Output: 2 1 7 3 10 2 5 4 9 Input: mat[][] = {{1, 3, 5, 6, 7}, {3, 5, 3, 2, 1}, {1, 2, 3, 4, 5}, {7, 9, 2, 1, 6}, {9, 1, 5,

Maximum possible middle element of the array after deleting exactly k elements

Given an integer array of size n and a number k. If the indexing is 1 based then the middle element of the array is the element at index (n + 1) / 2, if n is odd otherwise n / 2. The task is to delete exactly k elements from the array in such a way that the middle element of the reduced array is as maximum as possible. Find the maximum possible mid

Count of triplets of numbers 1 to N such that middle element is always largest

Given an integer N, the task is to count the number of ways to arrange triplets (a, b, c) within [1, N] in such a way such that the middle element is always greater than left and right elements. Example: Input: N = 4 Output: 8 Explanation For the given input N = 4 number of possible triplets are:{1, 3, 2}, {2, 3, 1}, {2, 4, 3}, {3, 4, 2}, {1, 4, 3}

Article Tags :

Practice Tags :