How to Delete Middle Element from a Stack

Delete Middle Element from a Stack

A stack is a linear data structure that works on the principle of "last in, first out" (LIFO). It allows operations like pushing (adding) and popping (removing) elements from the top of the stack. In this lesson, we will learn how to delete the middle element from a stack. For example, if the stack is [1, 2, 3, 4, 5], the middle element 3 should be removed, leaving [1, 2, 4, 5].

The middle element is the one that divides the stack into two equal halves. If the stack has an even number of elements, we consider the lower middle element as the middle. Since stacks do not provide direct access to elements, we use a recursive approach to remove the middle element.

This problem is often asked in coding interviews to test your understanding of recursion and stack operations.

Steps to Delete the Middle Element from a Stack

• Calculate the middle index. Find the index of the middle element based on the size of the stack.
• Use recursion to traverse the stack. Start removing elements from the top until you reach the middle index.
• Remove the middle element. When you reach the middle index, do not push the element back onto the stack.
• Rebuild the stack. Push back the remaining elements in reverse order as you return from the recursion.
• Return the modified stack. The middle element will be removed, and the stack will maintain its original order.

Have you ever tried to pull out a book from the middle of a stack without making the other books fall? In programming, sometimes you need to remove something from the middle of a stack, like changing a step in the middle of a process. This can be tricky because stacks work in a Last-In-First-Out (LIFO) way.

What is a stack?

A stack is a collection of items that follows a simple rule: the last item you put in is the first one you take out. Think of it like a stack of plates—you can only take the top plate without moving the others.

Why remove the middle item?

Imagine you’re following a series of steps in an app, and you realize there’s a mistake in the middle. Instead of starting over, it would be easier to just remove that one wrong step.

Basic stack operations

Before we get into the solution, let’s go over what you can usually do with a stack:

• Push: Add an item to the top.
• Pop: Remove the top item.
• Size: Find out how many items are in the stack.
• Empty: Check if the stack has no items.

Now, let’s look at how to remove the middle item from a stack.

Simple approach

One simple way is to pop items from the stack until you reach the middle. This works, but it’s not very efficient because it messes up the order of the items.

Better approach

A better way is to remove the middle item without messing up the order. You can do this by using another temporary stack or by using recursion.

How to do it in code

Here’s how you can do this in three common programming languages: Python, Java, and C++.

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
def delete_middle(stack):
    temp_stack = []
    middle_index = len(stack) // 2
    for _ in range(middle_index):
        temp_stack.append(stack.pop())
    stack.pop()  # Remove the middle item
    while temp_stack:
        stack.append(temp_stack.pop())

# Example
stack = [1, 2, 3, 4, 5]
delete_middle(stack)
print(stack)  # Output: [1, 2, 4, 5]

Java code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Stack;

public class StackManipulation {
    public static void deleteMiddle(Stack<Integer> stack) {
        Stack<Integer> tempStack = new Stack<>();
        int middleIndex = stack.size() / 2;
        for (int i = 0; i < middleIndex; i++) {
            tempStack.push(stack.pop());
        }
        stack.pop();  // Remove the middle item
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        deleteMiddle(stack);
        System.out.println(stack);  // Output: [1, 2, 4, 5]
    }
}

C++ code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <stack>
using namespace std;

void deleteMiddle(stack<int>& st) {
    stack<int> temp;
    int middleIndex = st.size() / 2;
    for (int i = 0; i < middleIndex; ++i) {
        temp.push(st.top());
        st.pop();
    }
    st.pop(); // Remove the middle item
    while (!temp.empty()) {
        st.push(temp.top());
        temp.pop();
    }
}

int main() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);
    deleteMiddle(st);

    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0; // Output: 5 4 2 1
}

Conclusion

Removing the middle item from a stack without messing up the rest takes some care. Learning how to do this will help you get better at programming and solving problems with data structures.