# How to Delete the Middle Element of a Stack?

How to Delete the Middle Element of a Stack?

## Introduction

Deleting, inserting, searching, and popping are some basic operations done in the stack data structure. There are a whole lot of problems available with these operations. For example, Inserting element at the bottom of a stack

## Problem Statement

Given a stack, delete the middle element of it without using any additional data structure. You can use basic stack operations like push(), pop() and empty().

For example :

Note: We’ll be deleting and returning the same stack. No new stack will be created.

## Solution Approach

The idea is to tackle it using Recursion. We will keep removing the elements one by one from the top of the stack recursively and then at the end push all of them except the middle one.

The steps are as follows :

Before directly jumping to the solution, we suggest you try and solve this delete middle element of a stack on Codestudio.

## Implementation

Let’s see the implementation of the above approach.

```#include <bits/stdc++.h>
using namespace std;

// Function that deletes the middle of the stack of size n. Current is current
// position we’re on
void deleteMiddle(stack<int> &s, int n,int current)
{
// If stack becomes empty or all items already are traversed
if (s.empty() || current == n)
return;

// Remove current item
int x = s.top();
s.pop();

// Call for removing the other items
deleteMiddle(s, n, current+1);

// Push all the elements back other than the middle one
if (current != n/2)
s.push(x);
}

int main()
{
stack<int> s;

//push elements into the stack
s.push(5);
s.push(6);
s.push(7);
s.push(8);
s.push(9);
s.push(10);
s.push(11);
int current = 0;
deleteMiddle(s, s.size(),current);

// Printing stack after deletion of the middle element.
while (!s.empty())
{
int p = s.top();
s.pop();
cout << p << " ";
}
return 0;

}
```

Output

`11 10 9 7 6 5`

8 was the middle element so it has been removed.

Time Complexity

O(n), where n is the size of the stack.

Reason : Since we’re iterating over the stack recursively by making only one recursive call, which takes O(n) time and popping and pushing operations take only O(1) time, the overall time complexity will be O(n).

Space Complexity

O(n), where n is the size of the stack.

Reason: We haven’t used any other data structure or any other stack. Therefore, the only space taken is the space to store the elements in the stack, i.e; the size of the stack.

If you’ve made it this far, congratulations, Champ. The problem of “Delete middle element of stack ” is now resolved. If you haven’t already submitted it to CodeStudio. Without further ado, have it accepted as early as possible.

When the stack is empty and we are trying to remove an element from the stack then the condition is called as?

In a stack, if a user tries to remove an element from the empty stack then it is called an underflow.

What is the term used to delete an element from the stack?

“Pop” is the term used to delete an element from the stack.

Where can I submit my “Delete middle element of a stack” code?

You can submit your code on CodeStudio and get it accepted right away.

Are there more Data Structures and Algorithms problems in CodeStudio?

Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

## Key Takeaways

As mentioned earlier, questions related to basic stack operations, inserting and deleting are prevalent.

These questions are asked during various coding contests as well as placements tests.

We discussed one such problem: delete middle element of a stack, along with its approach and implementation in C++, in this article.

Another similar problem is Insert An Element At Its Bottom In A Given Stack . Don’t forget to try it out as it’ll help you understand the operations well.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

By: Shreya Deep