Delete middle element of Stack

In this article, we discuss an iterative and recursive approach to delete the middle element of a stack.

Table of contents:

1. A brief introduction to Stacks
2. Problem Statement
3. Iterative Approach
4. Recursive Approach
5. Time and Space Complexity Analysis

Pre-requisite:

• Stack data structure
• Delete middle element of Queue

A brief introduction to Stacks

A stack is a linear data structure that follows LIFO(last in first out).
Picture a stack of plates, the last to be stacked(push) is the first to be removed(pop).

Operations on a stack include

Push: Adding an element to the top of the stack. An overflow occurs when stack is full.
Pop: Removing an element from the top of the stack. An underflow occurs when that stack is empty.
Peek/top: Return the top element of the stack.
isEmpty: Returns a boolean, true if the stack is empty, false otherwise.

All operations take constant time seeing as there are no iterations.

Stacks have various applications such as redo/undo features in text editors, backtracking algorithms(N-Queen), graph algorithms(topological sort) and more.

Problem Statement

Problem statement: We are given a stack and we are to delete the middle element using only stack operations.

Input: stack[] = [1, 2, 3, 4, 5] n = 5, mid = 3.
Output: [1, 2, 4, 5]

Explanation
The stack size is an odd number, therefore the middle element is 3.

Input: stack[] = [1, 2, 4, 6, 7, 8] n = 6, mid = 4.
Output: [1, 2, 6, 7, 8]

Explanation
The stack size is an even number thus we have two elements in the middle that is 4 and 6, we remove the first to appear(4).

Iterative Approach

We use a loop and a temporary stack where we shall store elements of the original stack excluding the middle element.
The push elements from the temporary stack to main stack.
Finally the main stack will have its original elements without the middle element.

Steps

1. Initialize a temporary stack and curr variable to store current position.
2. Loop through the stack while it has elements and pop elements.
3. Push the elements to the temporary stack excluding the mid element stack-size / 2.
4. Use another loop to traverse the temporary stack and push its elements to the main stack.
5. The main stack now has all its previous elements excluding the mid element.

Code

#include<iostream>
#include<stack>

using std::stack;
using std::cout;
using std::endl;

class RemoveMid{
    public:
        //iterative approach
        void removeMidIter(stack<int> &stk){
            //temporary stack
            stack<int> temp;
            int n = stk.size(), curr = 0;
            //pop from main stack and push to temp stack except where curr = n/2
            while(!stk.empty()){
                int i = stk.top();
                stk.pop();
                if(curr != n/2){
                    temp.push(i);
                }
                curr += 1;
            }
            //pop from temp and push to main stack, no mid element
            while(!temp.empty()){
                int t = temp.top();
                stk.push(t);
                temp.pop();
            }
        }

        void printStack(stack<int> stack){
            while(!stack.empty()){
                int s = stack.top();
                stack.pop();
                cout << s << " ";
            }
            cout << endl;
        }
};

int main(){
    RemoveMid rm;
    stack<int> stack;

    for(int i = 1; i <= 7; i++)
        stack.push(i);

    rm.printStack(stack);

    rm.removeMidIter(stack);

    rm.printStack(stack);
    return 0;
}

Recursive Approach

We shall recursion whereby we pop elements from the stack and push them back to the stack this time skipping the middle element, we use curr variable to store the current position.

The base case is when stack is empty or curr == stack-size.
Finally we should have a stack without the middle element.
We perform this operation without using any additional data structures ideally but recursion uses the call stack internally.

Steps:

1. Initialize current variable to store the current position.
2. Pop the stack.
3. Recursively call the function with current incremented by 1.
4. Repeat the above steps until the stack is empty or current is equal to stack size.
5. The stack is empty therefore we have popped all elements of the stack.
6. Push elements back to stack one by one except where current is n/2, this is the mid element.
7. Finally we have a stack without the middle element.

Code

#include<iostream>
#include<stack>

using std::stack;
using std::cout;
using std::endl;

class RemoveMid{
    public:
        
        //recursive approach
        void removeMidRec(stack<int> &stk, int n, int curr = 0){
            //base case (stack is empty, all elements popped)
            if(stk.empty() || curr == n)
                return;

            //pop current element
            int i = stk.top();
            stk.pop();

            //recursively remove other elements
            removeMidRec(stk, n, curr+1);

            //add elements back to stack except mid element
            if(curr != n/2)
                stk.push(i);
        }

        void printStack(stack<int> stack){
            while(!stack.empty()){
                int s = stack.top();
                stack.pop();
                cout << s << " ";
            }
            cout << endl;
        }
};

int main(){
    RemoveMid rm;
    stack<int> stack;

    for(int i = 1; i <= 7; i++)
        stack.push(i);

    rm.printStack(stack);

    rm.removeMidRec(stack, stack.size());

    rm.printStack(stack);
    return 0;
}

Output

7 6 5 4 3 2 1 
7 6 5 3 2 1 

Time and Space Complexity Analysis

All stack operations take constant time and traversing the stack of size n takes O(N) time complexity.

We use N space to store a stack of size n therefore the space complexity is also linear.

This is true for both iterative and recursive approaches.

Questions

What is the time complexity of stack operations?
What is maximum recursion depth?