{"id":9623,"date":"2022-09-12T07:17:52","date_gmt":"2022-09-12T07:17:52","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9623"},"modified":"2023-05-11T12:28:57","modified_gmt":"2023-05-11T12:28:57","slug":"delete-middle-element-of-the-stack","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/delete-middle-element-of-the-stack\/","title":{"rendered":"Delete Middle Element of the Stack"},"content":{"rendered":"

\"\"<\/p>\n

In computer science, a stack is an abstract data type that represents a collection of elements, where the addition or removal of elements follows a Last-In-First-Out (LIFO) order. That is, the last element that was added to the stack is the first one to be removed.<\/p>\n

To delete middle element of a stack refers to removing the element that is located in the middle of the stack. This can be a useful operation in some scenarios, such as when implementing algorithms that require removing a specific element from a stack, or when the stack contains redundant elements that need to be removed.<\/p>\n

However, deleting the middle element of a stack can be challenging since stacks do not provide direct access to elements in the middle. Therefore, the implementation of this operation typically requires additional data structures or algorithms that traverse the stack to locate and remove the middle element.<\/p>\n

How to Delete Middle Element of the Stack?<\/h2>\n

Given a stack of integers , delete the middle element of the stack using only standard stack<\/a> operations like push , pop , size , empty . If the size of the stack is even then delete the lower element .<\/p>\n

NOTE :<\/strong> You can also not use any other data structure .<\/p>\n

Sample example :<\/strong><\/p>\n

\"\"<\/p>\n

In the first example , the size of the stack is odd and 3 is the middle element , we will delete it .
\nIn the second example , the size of the stack is even , 3 and 4 both are the middle element . 4 is lower in the stack so we will delete that .<\/p>\n

In this article we will try to understand different ways to delete the middle element of the stack .<\/p>\n

Approach to Find Middle Element from Stack<\/h2>\n

If the stack has N elements , then we need to somehow store N\/2 elements of the stack and then delete (N\/2 + 1)-th element of the stack . Then we can push the top N\/2 elements that we have stored . To store N\/2 elements we have two methods: either we can go for an interactive approach and use a temporary stack or we can go for a recursive approach and use a recursive stack . Let\u2019s try to understand both .<\/p>\n

Algorithm for Iterative Approach<\/h3>\n
    \n
  1. Create an empty temporary stack temp.<\/li>\n
  2. Pop N\/2 elements from the given stack and Push it into the temp stack.<\/li>\n
  3. Pop top of the given stack , this is the targeted middle element .<\/li>\n
  4. Pop all elements from the temp stack and Push it into the given stack .<\/li>\n
  5. This will be the final stack after deleting the middle element .<\/li>\n<\/ol>\n

    Dry Run to Find Middle Element from Stack<\/h3>\n

    \"\"<\/p>\n

    Code Implementation<\/h3>\n

    Time Complexity :<\/strong> O(N)<\/p>\n

    Space Complexity :<\/strong> O(N)<\/p>\n

    Algorithm for Recursive Approach<\/h3>\n
      \n
    1. Create a recursive function which will accept the current stack and initial size of the input stack .<\/li>\n
    2. In each call we first check if N\/2 elements have already been deleted , then the top of stack will be the targeted middle element , we will pop it and stop the recursive call<\/li>\n
    3. Else we pop the top of stack and store it into a variable x , and do the recursive call for the current stack after popping. <\/li>\n
    4. Once the recursive call completes , push x into the stack .<\/li>\n
    5. The stack obtained at the end of the call is the final required stack .<\/li>\n<\/ol>\n

      Code Implementation<\/h3>\n\t\t\t\t\t\t