Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Implementation
4.
Frequently asked questions
4.1.
When the stack is empty and we are trying to remove an element from the stack then the condition is called as?
4.2.
What is the term used to delete an element from the stack?
4.3.
Where can I submit my “Delete middle element of a stack” code?
4.4.
Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Delete Middle Element Of The Stack

Author Shreya Deep
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Deleting a 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 : 

INPUT : STACK [ ] = [ 1 , 2 , 3 , 4 , 5 ] , N = 5OUTPUT:  [ 1 , 2 , 4,  5 ]The above example contains an odd number of elements, hence the middle element is clearly the N / 2th element, which is removed from the stack in the output.

INPUT : STACK [ ] = [ 5, 6, 7, 8 ] , N = 4OUTPUT:  [ 5, 7, 8 ]The above example contains an even number of elements, so out of the two middle elements, we consider the one which occurs first. Hence, the middle element would be (N / 2 - 1) element, which is 6 and is removed from the stack in the output.

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 :

Declare and initialize a variable named current to 0. This “current” will keep record of the position we are at now. Pop the top element of the stack. Call the deleteMiddle function after incrementing current by one( which signifies that we are moving on to the next position). Keep repeating steps 2 and 3 until the stack is not empty or current is not equal to n. Once the stack is empty or current==n, means that we’ve popped every element of the stack. Now, keep pushing back the elements one by one except for the case where curr==n/2.  Thus we have the stack now with all the elements except for the middle one.


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

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

The Time Complexity is 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

The Space Complexity is 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 Coding Ninjas Studio. Without further ado, have it accepted as early as possible.

Must Read Stack Operations

Frequently asked questions

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 as 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 Coding Ninjas Studio and get it accepted right away.

Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?

Yes, Coding Ninjas Studio 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.

Conclusion

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

We discussed one such problem: deleting the 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.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

You can also consider our Mern Stack Course to give your career an edge over others.

Happy Coding!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass