Delete Middle Element of Stack.

Given a stack of integers. The task is to delete the middle element from the stack without using extra space. The middle element is defined as the element at position (size of stack / 2 +1). Write a function/method that takes the stack as input and modifies it to delete the middle element.

Example:

Input:  [1, 2, 3, 4, 5]

Output: [1, 2, 4, 5]

Explanation: The middle element is 3, and after deletion, the stack becomes [1, 2, 4, 5].

Input:  [10, 20, 30, 40, 50, 60]

Output: [10, 20, 30, 50, 60]

Explanation: The middle element is 40, and after deletion, the stack becomes [10, 20, 30, 50, 60].

It is very easy to delete the middle element of the given stack by using any extra data structure. Still, the main challenge of this problem is to solve this without using any additional space. Actually, that is also quite simple if our powerful programming tool known as recursion. Before moving to the recursive solution to delete the middle element of the stack. Let's check a simple brute-force solution for this.

Brute Force Approach to Delete Middle Element of Stack.

In this approach, we will use another auxiliary stack or a list to store the given stack element until we reach the middle element and then we will remove (pop) the middle element from the stack and then push back all the elements of the auxiliary stack back to the main stack.

Algorithm Steps:

• Create a stack auxStack to temporarily store elements.
• Calculate the position of the middle element (middle = size / 2 +1).
• Iterate over the first half of the original stack (up to the element just before the middle) and Push each element to the auxStack and pop it from the original stack.
• Skip the middle element of the stack and pop it from the original stack.
• Pop elements from the auxStack and push them back to the original stack.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code implementation to delete middle element of stack
// Brute force approach using extra space
#include <iostream>
#include <stack>
using namespace std;

// Function to delete the middle element of a stack without recursion
void deleteMiddle(stack<int>& s) {
    int size = s.size();
    int middle = size / 2 + 1;

    stack<int> auxStack;

    // Push the first half of elements to the auxiliary stack
    for (int i = 0; i < middle - 1; i++) {
        auxStack.push(s.top());
        s.pop();
    }

    // Skip the middle element
    s.pop();

    // Push the elements back to the original stack
    while (!auxStack.empty()) {
        s.push(auxStack.top());
        auxStack.pop();
    }
}

// Function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    // Example usage
    stack<int> myStack;

    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(5);

    cout << "Original Stack: ";
    printStack(myStack);

    // Delete the middle element without recursion
    deleteMiddle(myStack);

    cout << "Stack after deleting middle element: ";
    printStack(myStack);

    return 0;
}

// Java code implementation to delete middle element of stack
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> myStack = new Stack<>();

        // Push elements onto the stack
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);

        System.out.println("Original Stack: " + myStack);

        // Delete the middle element without recursion
        deleteMiddle(myStack);

        System.out.println("Stack after deleting middle element: " + myStack);
    }

    // Function to delete the middle element of a stack without recursion
    public static void deleteMiddle(Stack<Integer> s) {
        int size = s.size();
        int middle = size / 2 + 1;

        Stack<Integer> auxStack = new Stack<>();

        // Push the first half of elements to the auxiliary stack
        for (int i = 0; i < middle - 1; i++) {
            auxStack.push(s.pop());
        }

        // Skip the middle element
        s.pop();

        // Push the elements back to the original stack
        while (!auxStack.isEmpty()) {
            s.push(auxStack.pop());
        }
    }
}

# Python code to delete middle element of stack
def delete_middle(s):
size = len(s)
middle = size // 2 + 1

aux_stack = []

# Push the first half of elements to the auxiliary stack
for i in range(middle - 1):
    aux_stack.append(s.pop())

# Skip the middle element
s.pop()

# Push the elements back to the original stack
while aux_stack:
    s.append(aux_stack.pop())

# Example usage
my_stack = [1, 2, 3, 4, 5]

print("Original Stack:", my_stack)

# Delete the middle element without recursion
delete_middle(my_stack)

print("Stack after deleting middle element:", my_stack)

// C# code implementation to delete middle element of stack
using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Stack<int> myStack = new Stack<int>();

        // Push elements onto the stack
        myStack.Push(1);
        myStack.Push(2);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);

        Console.WriteLine("Original Stack: " + string.Join(" ", myStack));

        // Delete the middle element without recursion
        DeleteMiddle(myStack);

        Console.WriteLine("Stack after deleting middle element: " + string.Join(" ", myStack));
    }

    // Function to delete the middle element of a stack without recursion
    public static void DeleteMiddle(Stack<int> s) {
        int size = s.Count;
        int middle = size / 2 + 1;

        Stack<int> auxStack = new Stack<int>();

        // Push the first half of elements to the auxiliary stack
        for (int i = 0; i < middle - 1; i++) {
            auxStack.Push(s.Pop());
        }

        // Skip the middle element
        s.Pop();

        // Push the elements back to the original stack
        while (auxStack.Count > 0) {
            s.Push(auxStack.Pop());
        }
    }
}

Output:

Original Stack: 5 4 3 2 1
Stack after deleting middle element: 5 4 2 1

• Time Complexity: O(n) where n is the number of elements present in the given stack.
• Space Complexity: O(n) as we are using an extra stack to delete the middle element of the stack.

Delete Middle Element of the Stack Using Recursion.

We can delete the middle element of the stack using recursion without using any extra space. In this approach, we will recursively pop the stack element, and while unwinding we will push back all the elements except the middle element.

Algorithm Steps:

• The base case of our recursive call is when our stack gets empty.
• Pop an element from the stack and recursively call the function.
• While unwinding from the recursive calls, increment a counter to keep track of the number of elements.
• If the counter indicates the middle element, skip pushing it back onto the stack.
• While unwinding, push the elements back onto the stack.

Below is the code implementation of the above recursive approach:

C++ Java Python C#

// C++ code for recurisvely delete middle element of stack
#include <iostream>
#include <stack>

using namespace std;

// Function to delete the middle element of a stack using recursion
void deleteMiddle(stack<int>& s, int current, int middle) {
    // Base case: stack is empty
    if (s.empty()) {
        return;
    }

    // Recursive call: pop an element and make a recursive call
    int temp = s.top();
    s.pop();
    deleteMiddle(s, current + 1, middle);

    // Count elements and skip pushing the middle element
    if (current != middle) {
        s.push(temp);
    }
}

// Function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> myStack;

    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(5);

    cout << "Original Stack: ";
    printStack(myStack);

    int middle = myStack.size() / 2;
    
    // Delete the middle element using recursion
    deleteMiddle(myStack, 0, middle);

    cout << "Stack after deleting middle element: ";
    printStack(myStack);

    return 0;
}

import java.util.Stack;

public class Main {
  public static void main(String[] args) {
      Stack<Integer> myStack = new Stack<>();

      // Push elements onto the stack
      myStack.push(1);
      myStack.push(2);
      myStack.push(3);
      myStack.push(4);
      myStack.push(5);

      System.out.println("Original Stack: " + myStack);

      int middle = myStack.size() / 2;

      // Delete the middle element using recursion
      deleteMiddle(myStack, 0, middle);

      System.out.println("Stack after deleting middle element: " + myStack);
  }

  // Function to delete the middle element of a stack using recursion
  public static void deleteMiddle(Stack<Integer> s, int current, int middle) {
      if (s.isEmpty()) {
          return;
      }

      int temp = s.pop();
      deleteMiddle(s, current + 1, middle);

      if (current != middle) {
          s.push(temp);
      }
  }
}

# Python program to delete middle element of stack using Recursive

def delete_middle(s, current, middle):
# Base case: stack is empty
if not s:
    return

# Recursive call: pop an element and make a recursive call
temp = s.pop()
delete_middle(s, current + 1, middle)

# Count elements and skip pushing the middle element
if current != middle:
    s.append(temp)

# Example usage
my_stack = [1, 2, 3, 4, 5]

print("Original Stack:", my_stack)
middle = len(my_stack) // 2

# Delete the middle element using recursion
delete_middle(my_stack, 0, middle)

print("Stack after deleting middle element:", my_stack)

//C# code to delete middle element of stack using Recursion
using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Stack<int> myStack = new Stack<int>();

        // Push elements onto the stack
        myStack.Push(1);
        myStack.Push(2);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);

        Console.WriteLine("Original Stack: " + string.Join(" ", myStack));

        int middle = myStack.Count / 2;

        // Delete the middle element using recursion
        DeleteMiddle(myStack, 0, middle);

        Console.WriteLine("Stack after deleting middle element: " + string.Join(" ", myStack));
    }

    // Function to delete the middle element of a stack using recursion
    public static void DeleteMiddle(Stack<int> s, int current, int middle) {
        if (s.Count == 0) {
            return;
        }

        int temp = s.Pop();
        DeleteMiddle(s, current + 1, middle);

        if (current != middle) {
            s.Push(temp);
        }
    }
}

Output:

Original Stack: 5 4 3 2 1 
Stack after deleting middle element: 5 4 2 1 

• Time Complexity: O(n) where n is the number of elements in the stack.
• Space Complexity: O(n) using auxiliary space for Recursion.

Types of Recursion in C++ with Examples

Recursion is a process in which a function calls itself directly or indirectly to solve a problem. In this article, we will learn Recursion in C++ and its implementation.

Syntax:

int fun()
{
   ....
   fun()
}

Recursion allows the function to repeat a specific action until a specific condition is met and the function stops calling itself when the specific condition is met that stopping condition is also known as the base condition.  

Let's understand recursion with one standard example: finding the factorial of a given number. 

C++ Program to find the Factorial of a number.

#include<iostream>
using namespace std;

//function to find factorial
int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main()
{
    int num;

    cout<<"Enter a number: ";
    cin>>num;
    cout<<"Factorial of given number: "<<factorial(num);

    return 0;
}

Output:

Enter a number: 5
Factorial of given number: 120

Working of Recursion.

In the above example, the factorial function calculates the factorial of n by making a recursive call to itself with n-1 as the argument. The if statement checks for the base case, which is when n is equal to 0 and returns 1 in that case. When the base case is not reached, the function calculates n * factorial(n-1), and this continues until the base case is reached.

Recursion

We need to follow two simple steps to solve any recursion problem and these are:

Step 1: Divide the problem into smaller sub-problem. 

Finding the solution for a smaller sub-problem is easy compared to finding the solution for a single large problem. In recursion, we keep dividing the problem into smaller sub-problem until we find the smallest sub-problem.

Step 2: Specify the base condition to stop the recursion.

The base condition is the one that doesn't require calling the same function again and it helps in stopping the recursion. In our case, finding the factorial of 0 is the base case. 

Types of Recursion.

• Direct Recursion
• Indirect Recursion
• Tail Recursion
• Non-Tail Recursion

1. Direct Recursion.

Direct recursion is a condition in which the function calls itself directly from the inside.

//Example of direct Recursion
void fun()
{
    //some code

    fun();

}

2. Indirect Recursion.

Indirect recursion is a condition in which the first function calls the second function and the second function again calls the first function.

//Example of indirect Recursion
void fun_1()
{
    //some code
    fun_2();
}

void fun_2()
{
    //some code
    fun_1();
}

3. Tail Recursion.

A recursion function is said to be a tail recursion if the recursion call is the last thing done by the function. There is no need to keep a record of the previous state.

Example: 

//Example of Tail Recursion in C++
#include<iostream>
using namespace std;

//recursive function
int fun(int n)
{
    if(n == 0)
      return 0;
    else
      cout<<n<<" ";
    return fun(n - 1);    
}
int main(){
    //function call
    fun(3);

    return 0;
}

Output:

3 2 1

4. Non-Tail Recursion.

A recursion function is said to be non-tail recursion when the same function call is not the last thing done by the function.  After returning back there is some statement left to evaluate. 

Example:

//Non-Tail Recursion Example in C++
#include<iostream>
using namespace std;

void fun(int n)
{
  if(n == 0)
    return;

  fun(n - 1);
  cout<<n<<" ";

}

int main()
{
  //function call
  fun(3);

  return 0;
}

Output:

1 2 3

Conclusion.

• Every recursion program can be written as iterative.
• Every recursion program can be modeled into an iterative program but recursive programs are more elegant and require relatively fewer lines of code.
• The recursive program requires more space in memory than iterative programs.

Tower of Hanoi using Recursion.

 Tower of Hanoi is one of the most popular recursive problems that everyone practices when they start learning the recursion concept. In this problem, we have three pillars and we have to move some disks from one pillar to another pillar. 

Let say, we have three pillars named A as source pillar, B as a temporary pillar, and C as a destination pillar. Pillar A has a finite number of disks and these disks are arranged in decreasing order of their size. We have to move all the disks from source pillar A to destination pillar C using temporary pillar B but you have to follow two conditions while doing this-

• You can move only one disk from one pillar to another at a time. 
• A larger disk cannot be placed on a smaller disk.

The approach of solving tower of Hanoi problem recursively, 

1. Move upper (n-1) disks from A to B using C as the temporary pillar. 
2. Move nth disk from A to C. 
3. Move (n-1) disks from B to C using A as the temporary pillar. 

The base condition of our recursive approach is when we have to move only one disk from source to destination pillar and return. 

C++ Program to Tower of Hanoi Problem. 

#include <iostream>

using namespace std;

void tofh(int ndisk, char source, char temp, char dest)

{

    if(ndisk == 1)

    {

        cout<<"Move disk "<<ndisk<<" from "<<source<<" to "<<dest<<endl;

        return; 

    }

    tofh(ndisk-1, source, dest, temp);

    cout<<"Move disk "<<ndisk<<" from "<<source<<" to "<<dest<<endl;

    tofh(ndisk-1, temp, source, dest);

}

int main() {

    char source = 'A', temp = 'B', dest = 'C';

    int ndisk;

    cout<<"\nEnter the number of disks: ";

    cin>>ndisk;

    cout<<"\nSequence of steps: \n";

    tofh(ndisk, source, temp, dest);

    return 0;

}

Output: 

Enter the number of disks: 3

Sequence of steps: 

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C