Delete Middle Element of a Stack in Java

In order to delete the middle element of a stack, then first we need to remove the elements above the middle element. After removing the middle element, we restore the elements above it to maintain the original sequence. We can achieve this using a recursive approach, as explained step-by-step below.

We cannot delete the middle element of the stack directly because, according to the stack property, we can perform only push and pop operations on the top of the stack.

Steps to Delete the Middle Element of a Stack

Step 1: Determine the Position of the Middle Element, First of all, we need to determine the middle element of the stack following is the way to do so ?

• If the stack contains 9 elements (index 0 to 8), then the middle element is at position 4.
• If the stack contains an even number of elements (e.g., 4 elements), the first of the two middle elements will be deleted
• If the stack contains only one element, that element will be considered the middle element and deleted.

Step 2: We keep removing the top elements of the stack until we reach the middle element recursively.

Step 3: Once we reach the middle element, we simply pop it from the stack and then reassemble the stack to its original order.

Program

The following example deletes the middle element of a stack ?

import java.util.Stack;
public class Example {
   public static void deleteMidElement(Stack < Integer > stack, int currentIndex) {
      if (currentIndex == 0) {
         stack.pop();
         return;
      }

      int temp = stack.pop();
      deleteMidElement(stack, currentIndex - 1);
      stack.push(temp);

   }
   public static void main(String args[]) {
      int N;
      Stack <Integer> stack = new Stack < >
      ();
      stack.push(9);
      stack.push(10);
      stack.push(0);
      stack.push(5);
      stack.push(7);
      N = stack.size();
      N = N / 2;

      System.out.println("Stack before deleting middle element: " + stack);
      deleteMidElement(stack, N);
      System.out.println("Stack after deleting middle element: " + stack);
   }
}

Following is the output of the above program ?

Stack before deleting middle element: [9, 10, 0, 5, 7]
Stack after deleting middle element: [9, 10, 5, 7]

Explanation

In the main method, we called the deleteMidElement() method with the parameters stack and the index of the middle element.

In the method deleteMidElement(), we checked whether currentIndex==0, if it is true then stack's top is middle element, and if not, the top of stack is stored in a variable and deleteMidElement is invoked recursively, decrementing currentIndex by one each time, and then pushed back the stored element.