Delete Middle Element from a Stack

Mon Aug 19 2024

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

python

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

Java code

java

1import java.util.Stack;
2
3public class StackManipulation {
4    public static void deleteMiddle(Stack<Integer> stack) {
5        Stack<Integer> tempStack = new Stack<>();
6        int middleIndex = stack.size() / 2;
7        for (int i = 0; i < middleIndex; i++) {
8            tempStack.push(stack.pop());
9        }
10        stack.pop();  // Remove the middle item
11        while (!tempStack.isEmpty()) {
12            stack.push(tempStack.pop());
13        }
14    }
15
16    public static void main(String[] args) {
17        Stack<Integer> stack = new Stack<>();
18        stack.push(1);
19        stack.push(2);
20        stack.push(3);
21        stack.push(4);
22        stack.push(5);
23        deleteMiddle(stack);
24        System.out.println(stack);  // Output: [1, 2, 4, 5]
25    }
26}

C++ code

cpp

1#include <iostream>
2#include <stack>
3using namespace std;
4
5void deleteMiddle(stack<int>& st) {
6    stack<int> temp;
7    int middleIndex = st.size() / 2;
8    for (int i = 0; i < middleIndex; ++i) {
9        temp.push(st.top());
10        st.pop();
11    }
12    st.pop(); // Remove the middle item
13    while (!temp.empty()) {
14        st.push(temp.top());
15        temp.pop();
16    }
17}
18
19int main() {
20    stack<int> st;
21    st.push(1);
22    st.push(2);
23    st.push(3);
24    st.push(4);
25    st.push(5);
26    deleteMiddle(st);
27
28    while (!st.empty()) {
29        cout << st.top() << " ";
30        st.pop();
31    }
32    return 0; // Output: 5 4 2 1
33}

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.