# Delete middle element of a stack

The problem statement is to delete the middle element of a stack. Given a stack, we need to remove the element that is located at the middle position of the stack. If the stack contains an odd number of elements, the middle element is the one located at (n/2)+1, where n is the total number of elements in the stack. If the stack contains an even number of elements, there are two middle elements, and we can choose either to remove.

## Example

Let's say we have the following stack: `[1, 2, 3, 4, 5, 6, 7]`. We want to delete the middle element, which is `4`. After the operation, the stack should look like this: `[1, 2, 3, 5, 6, 7]`.

## Idea to Solve the Problem

To delete the middle element, we can use the following approach:

1. First, we find the middle element's position in the stack, which is (n/2)+1 for odd-sized stacks, where n is the number of elements in the stack.
2. Then, we use a recursive function to remove the element located at the middle position.
3. To achieve this, we remove elements one by one from the top of the stack until we reach the middle position.
4. After removing the middle element, we push back the previously removed elements to their original positions.

## Algorithm

1. Define a structure for the stack node, containing an element and a pointer to the next node.
2. Define a custom stack structure, containing the top node pointer and the size of the stack.
3. Implement functions for creating a new stack, creating a new node, checking if the stack is empty, pushing elements, peeking at the top element, and popping elements.
4. Implement a recursive function to remove the middle element:
• The function takes the stack, the middle position, and a counter as input.
• If the counter is equal to the middle position, remove the top element (the middle element).
• If the counter is less than the middle position, pop the top element, recursively call the function with an incremented counter, and then push back the popped element.
5. Create a function to handle the deletion of the middle element:
• Check if the stack is empty.
• Calculate the middle position (n/2)+1.
• Call the recursive function to remove the middle element.
6. Test the implementation by creating a stack, adding elements to it, and then deleting the middle elements one by one.

## Pseudocode

``````FUNCTION removeMiddle(stack, mid, counter):
IF counter == mid THEN
POP top element from stack  // Delete middle element
ELSE IF counter < mid AND stack is not empty THEN
element = PEEK top element from stack
POP top element from stack
CALL removeMiddle(stack, mid, counter + 1)  // Recursive call
PUSH element back to stack

FUNCTION deleteMiddle(stack):
IF stack is not empty THEN
mid = stack size / 2 + 1
CALL removeMiddle(stack, mid, 0)

FUNCTION main():
CREATE a new stack
PUSH elements into the stack
PRINT the stack elements
DELETE middle elements one by one and PRINT the updated stack after each deletion
``````

## Code Solution

``````// C program
// Delete middle element of a stack
#include <stdio.h>
#include <stdlib.h>

// Define stack node
struct StackNode
{
int element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
//Create a new node of stack
struct StackNode *newNode(int element, struct StackNode *next)
{
//Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = next;
}
return node;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
stack->top = newNode(element, stack->top);
stack->size++;
}
int peek(struct MyStack *stack)
{
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Remove middle element of stack
void removeMiddle(struct MyStack *stack, int mid, int counter)
{
if (counter == mid)
{
printf("\n Delete middle element : %d", peek(stack));
// Delete middle node
pop(stack);
}
else if (counter < mid && isEmpty(stack) == 0)
{
// When stack not empty and counter is less than middle position
// Get top element
int element = peek(stack);
// Remove top element
pop(stack);
// Recursively finding the middle element
removeMiddle(stack, mid, counter + 1);
push(stack, element);
}
}
// Handles the request to delete middle element of stack
void deleteMiddle(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
// Get middle element location
int mid = stack->size / 2;

removeMiddle(stack, mid, 0);
}
else
{
printf("\n Stack Is Empty \n");
}
}
// Print element of stack
void printData(struct MyStack *stack)
{
struct StackNode *temp = stack->top;
// iterate stack elements
while (temp != NULL)
{
// Display element value
printf("  %d", temp->element);
temp = temp->next;
}
printf("\n");
}
int main()
{
struct MyStack *stack = newStack();
push(stack, 7);
push(stack, 6);
push(stack, 5);
push(stack, 4);
push(stack, 3);
push(stack, 2);
push(stack, 1);
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
printf("\n Stack element \n");
printData(stack);
// delete operation
deleteMiddle(stack);
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
printf("\n After Delete stack \n");
printData(stack);
// delete operation
deleteMiddle(stack);

/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
printf("\n After Delete stack  \n");
printData(stack);
// delete operation
deleteMiddle(stack);
/*
After delete middle element
============
1 <- Top
2
6
7
*/
printf("\n After Delete stack \n");
printData(stack);
return 0;
}``````

#### Output

`````` Stack element
1  2  3  4  5  6  7

Delete middle element : 4
After Delete stack
1  2  3  5  6  7

Delete middle element : 5
After Delete stack
1  2  3  6  7

Delete middle element : 3
After Delete stack
1  2  6  7``````
``````/*
Java Program
Delete middle element of a stack
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
return this.top.element;
}
}
public class DeleteElement
{
public MyStack stack;
public DeleteElement()
{
this.stack = new MyStack();
}
// Print element of stack
public void printData()
{
StackNode temp = this.stack.top;
while (temp != null)
{
// Display element value
System.out.print("   " + temp.element);
temp = temp.next;
}
System.out.print("\n");
}
// Remove middle element of stack
public void removeMiddle(int mid, int counter)
{
if (counter == mid)
{
// When get middle element
System.out.print("\n Delete middle element : " + this.stack.peek() + "");
// Delete middle node
this.stack.pop();
}
else if (counter < mid && this.stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
int element = this.stack.peek();
// Remove top element
this.stack.pop();
// Recursively finding the middle element
removeMiddle(mid, counter + 1);
this.stack.push(element);
}
}
// Handles the request to delete middle element of stack
public void deleteMiddle()
{
if (this.stack.isEmpty() == false)
{
// Get middle element location
int mid = this.stack.size / 2;
removeMiddle(mid, 0);
}
else
{
System.out.print("\n Stack Is Empty \n");
}
}
public static void main(String[] args)
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
System.out.print("\n Stack element \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
System.out.print("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
System.out.print("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
System.out.print("\n After Delete stack \n");
}
}``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Delete middle element of a stack
*/
// Define stack node
class StackNode
{
public: int element;
StackNode *next;
StackNode(int element, StackNode *next)
{
this->element = element;
this->next = next;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
int peek()
{
return this->top->element;
}
};
class DeleteElement
{
public:
MyStack stack;
DeleteElement()
{
this->stack = MyStack();
}
// Print element of stack
void printData()
{
StackNode *temp = this->stack.top;
while (temp != NULL)
{
// Display element value
cout << "   " << temp->element;
temp = temp->next;
}
cout << "\n";
}
// Remove middle element of stack
void removeMiddle(int mid, int counter)
{
if (counter == mid)
{
// When get middle element
cout << "\n Delete middle element : " << this->stack.peek() << "";
// Delete middle node
this->stack.pop();
}
else if (counter < mid && this->stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
int element = this->stack.peek();
// Remove top element
this->stack.pop();
// Recursively finding the middle element
this->removeMiddle(mid, counter + 1);
this->stack.push(element);
}
}
// Handles the request to delete middle element of stack
void deleteMiddle()
{
if (this->stack.isEmpty() == false)
{
// Get middle element location
int mid = this->stack.size / 2;
this->removeMiddle(mid, 0);
}
else
{
cout << "\n Stack Is Empty \n";
}
}
};
int main()
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
cout << "\n Stack element \n";
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
cout << "\n After Delete stack \n";
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
cout << "\n After Delete stack \n";
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
cout << "\n After Delete stack \n";
return 0;
}``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````
``````// Include namespace system
using System;
/*
C# Program
Delete middle element of a stack
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
return this.top.element;
}
}
public class DeleteElement
{
public MyStack stack;
public DeleteElement()
{
this.stack = new MyStack();
}
// Print element of stack
public void printData()
{
StackNode temp = this.stack.top;
while (temp != null)
{
// Display element value
Console.Write("   " + temp.element);
temp = temp.next;
}
Console.Write("\n");
}
// Remove middle element of stack
public void removeMiddle(int mid, int counter)
{
if (counter == mid)
{
// When get middle element
Console.Write("\n Delete middle element : " + this.stack.peek() + "");
// Delete middle node
this.stack.pop();
}
else if (counter < mid && this.stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
int element = this.stack.peek();
// Remove top element
this.stack.pop();
// Recursively finding the middle element
removeMiddle(mid, counter + 1);
this.stack.push(element);
}
}
// Handles the request to delete middle element of stack
public void deleteMiddle()
{
if (this.stack.isEmpty() == false)
{
// Get middle element location
int mid = this.stack.size / 2;
removeMiddle(mid, 0);
}
else
{
Console.Write("\n Stack Is Empty \n");
}
}
public static void Main(String[] args)
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
Console.Write("\n Stack element \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
Console.Write("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
Console.Write("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
Console.Write("\n After Delete stack \n");
}
}``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````
``````<?php
/*
Php Program
Delete middle element of a stack
*/
// Define stack node
class StackNode
{
public \$element;
public \$next;

function __construct(\$element, \$next)
{
\$this->element = \$element;
\$this->next = \$next;
}
}
// Define a custom stack
class MyStack
{
public \$top;
public \$size;

function __construct()
{
//Set node values
\$this->top = null;
\$this->size = 0;
}
// Add node at the top of stack
public  function push(\$element)
{
\$this->top = new StackNode(\$element, \$this->top);
\$this->size++;
}
public  function isEmpty()
{
if (\$this->size > 0 && \$this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public  function pop()
{
if (\$this->size > 0 && \$this->top != null)
{
\$temp = \$this->top;
// Change top element of stack
\$this->top = \$temp->next;
// remove previous top
\$temp = null;
\$this->size--;
}
}
public  function peek()
{
return \$this->top->element;
}
}
class DeleteElement
{
public \$stack;

function __construct()
{
\$this->stack = new MyStack();
}
// Print element of stack
public  function printData()
{
\$temp = \$this->stack->top;
while (\$temp != null)
{
// Display element value
echo "   ". \$temp->element;
\$temp = \$temp->next;
}
echo "\n";
}
// Remove middle element of stack
public  function removeMiddle(\$mid, \$counter)
{
if (\$counter == \$mid)
{
// When get middle element
echo "\n Delete middle element : ". \$this->stack->peek() ."";
// Delete middle node
\$this->stack->pop();
}
else if (\$counter < \$mid && \$this->stack->isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
\$element = \$this->stack->peek();
// Remove top element
\$this->stack->pop();
// Recursively finding the middle element
\$this->removeMiddle(\$mid, \$counter + 1);
\$this->stack->push(\$element);
}
}
// Handles the request to delete middle element of stack
public  function deleteMiddle()
{
if (\$this->stack->isEmpty() == false)
{
// Get middle element location
\$mid = intval(\$this->stack->size / 2);
\$this->removeMiddle(\$mid, 0);
}
else
{
echo "\n Stack Is Empty \n";
}
}
}

function main()
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
echo "\n Stack element \n";
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
echo "\n After Delete stack \n";
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
echo "\n After Delete stack \n";
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
echo "\n After Delete stack \n";
}
main();``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````
``````/*
Node Js Program
Delete middle element of a stack
*/
// Define stack node
class StackNode
{
constructor(element, next)
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
peek()
{
return this.top.element;
}
}
class DeleteElement
{
constructor()
{
this.stack = new MyStack();
}
// Print element of stack
printData()
{
var temp = this.stack.top;
while (temp != null)
{
// Display element value
process.stdout.write("   " + temp.element);
temp = temp.next;
}
process.stdout.write("\n");
}
// Remove middle element of stack
removeMiddle(mid, counter)
{
if (counter == mid)
{
// When get middle element
process.stdout.write("\n Delete middle element : " + this.stack.peek() + "");
// Delete middle node
this.stack.pop();
}
else if (counter < mid && this.stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
var element = this.stack.peek();
// Remove top element
this.stack.pop();
// Recursively finding the middle element
this.removeMiddle(mid, counter + 1);
this.stack.push(element);
}
}
// Handles the request to delete middle element of stack
deleteMiddle()
{
if (this.stack.isEmpty() == false)
{
// Get middle element location
var mid = parseInt(this.stack.size / 2);
this.removeMiddle(mid, 0);
}
else
{
process.stdout.write("\n Stack Is Empty \n");
}
}
}

function main()
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
process.stdout.write("\n Stack element \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
process.stdout.write("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
process.stdout.write("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
process.stdout.write("\n After Delete stack \n");
}
main();``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````
``````#  Python 3 Program
#  Delete middle element of a stack

#  Define stack node
class StackNode :

def __init__(self, element, next) :
self.element = element
self.next = next

#  Define a custom stack
class MyStack :

def __init__(self) :
# Set node values
self.top = None
self.size = 0

#  Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1

def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True

#  Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = None
self.size -= 1

def peek(self) :
return self.top.element

class DeleteElement :

def __init__(self) :
self.stack = MyStack()

#  Print element of stack
def printData(self) :
temp = self.stack.top
while (temp != None) :
#  Display element value
print("   ", temp.element, end = "")
temp = temp.next

print(end = "\n")

#  Remove middle element of stack
def removeMiddle(self, mid, counter) :
if (counter == mid) :
#  When get middle element
print("\n Delete middle element : ", self.stack.peek() ,"", end = "")
#  Delete middle node
self.stack.pop()

elif(counter < mid and self.stack.isEmpty() == False) :
#  When stack not empty and counter is less than middle position
#  Get top element
element = self.stack.peek()
#  Remove top element
self.stack.pop()
#  Recursively finding the middle element
self.removeMiddle(mid, counter + 1)
self.stack.push(element)

#  Handles the request to delete middle element of stack
def deleteMiddle(self) :
if (self.stack.isEmpty() == False) :
#  Get middle element location
mid = int(self.stack.size / 2)
self.removeMiddle(mid, 0)
else :
print("\n Stack Is Empty ")

def main() :
#
#         Created Stack
#         ============
#             1 <- Top
#             2
#             3
#             4
#             5
#             6
#             7
#

print("\n Stack element ")
#  delete operation
#
#         After delete middle element
#         ============
#             1 <- Top
#             2
#             3
#             5
#             6
#             7
#

print("\n After Delete stack ")
#  delete operation
#
#         After delete middle element
#         ============
#             1 <- Top
#             2
#             3
#             6
#             7
#

print("\n After Delete stack ")
#  delete operation
#
#         After delete middle element
#         ============
#             1 <- Top
#             2
#             6
#             7
#

print("\n After Delete stack ")

if __name__ == "__main__": main()``````

#### Output

`````` Stack element
1    2    3    4    5    6    7

Delete middle element :  4
After Delete stack
1    2    3    5    6    7

Delete middle element :  5
After Delete stack
1    2    3    6    7

Delete middle element :  3
After Delete stack
1    2    6    7``````
``````#  Ruby Program
#  Delete middle element of a stack

#  Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next

def initialize(element, nextNode)
self.element = element
self.next = nextNode
end

end

#  Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top, :size

def initialize()
# Set node values
self.top = nil
self.size = 0
end

#  Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end

def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end

end

#  Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = nil
self.size -= 1
end

end

def peek()
return self.top.element
end

end

class DeleteElement
# Define the accessor and reader of class DeleteElement
attr_accessor :stack

def initialize()
self.stack = MyStack.new()
end

#  Print element of stack
def printData()
temp = self.stack.top
while (temp != nil)
#  Display element value
print("   ", temp.element)
temp = temp.next
end

print("\n")
end

#  Remove middle element of stack
def removeMiddle(mid, counter)
if (counter == mid)
#  When get middle element
print("\n Delete middle element : ", self.stack.peek() ,"")
#  Delete middle node
self.stack.pop()
elsif(counter < mid && self.stack.isEmpty() == false)
#  When stack not empty and counter is less than middle position
#  Get top element
element = self.stack.peek()
#  Remove top element
self.stack.pop()
#  Recursively finding the middle element
self.removeMiddle(mid, counter + 1)
self.stack.push(element)
end

end

#  Handles the request to delete middle element of stack
def deleteMiddle()
if (self.stack.isEmpty() == false)
#  Get middle element location
mid = self.stack.size / 2
self.removeMiddle(mid, 0)
else
print("\n Stack Is Empty \n")
end

end

end

def main()
#
#         Created Stack
#         ============
#             1 <- Top
#             2
#             3
#             4
#             5
#             6
#             7
#

print("\n Stack element \n")
#  delete operation
#
#         After delete middle element
#         ============
#             1 <- Top
#             2
#             3
#             5
#             6
#             7
#

print("\n After Delete stack \n")
#  delete operation
#
#         After delete middle element
#         ============
#             1 <- Top
#             2
#             3
#             6
#             7
#

print("\n After Delete stack \n")
#  delete operation
#
#         After delete middle element
#         ============
#             1 <- Top
#             2
#             6
#             7
#

print("\n After Delete stack \n")
end

main()``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7
``````
``````/*
Scala Program
Delete middle element of a stack
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode)
{
}
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
def peek(): Int = {
return this.top.element;
}
}
class DeleteElement(var stack: MyStack)
{
def this()
{
this(new MyStack());
}
// Print element of stack
def printData(): Unit = {
var temp: StackNode = this.stack.top;
while (temp != null)
{
// Display element value
print("   " + temp.element);
temp = temp.next;
}
print("\n");
}
// Remove middle element of stack
def removeMiddle(mid: Int, counter: Int): Unit = {
if (counter == mid)
{
// When get middle element
print("\n Delete middle element : " + this.stack.peek() );
// Delete middle node
this.stack.pop();
}
else if (counter < mid && this.stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
var element: Int = this.stack.peek();
// Remove top element
this.stack.pop();
// Recursively finding the middle element
this.removeMiddle(mid, counter + 1);
this.stack.push(element);
}
}
// Handles the request to delete middle element of stack
def deleteMiddle(): Unit = {
if (this.stack.isEmpty() == false)
{
// Get middle element location
var mid: Int = (this.stack.size / 2).toInt;
this.removeMiddle(mid, 0);
}
else
{
print("\n Stack Is Empty \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: DeleteElement = new DeleteElement();
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
print("\n Stack element \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
print("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
print("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
print("\n After Delete stack \n");
}
}``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````
``````/*
Swift 4 Program
Delete middle element of a stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ next: StackNode? )
{
self.element = element;
self.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
func peek()->Int
{
return self.top!.element;
}
}
class DeleteElement
{
var stack: MyStack;
init()
{
self.stack = MyStack();
}
// Print element of stack
func printData()
{
var temp: StackNode? = self.stack.top;
while (temp != nil)
{
// Display element value
print("   ", temp!.element, terminator: "");
temp = temp!.next;
}
print(terminator: "\n");
}
// Remove middle element of stack
func removeMiddle(_ mid: Int, _ counter: Int)
{
if (counter == mid)
{
// When get middle element
print("\n Delete middle element : ", self.stack.peek(), terminator: "");
// Delete middle node
self.stack.pop();
}
else if (counter < mid && self.stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
let element: Int = self.stack.peek();
// Remove top element
self.stack.pop();
// Recursively finding the middle element
self.removeMiddle(mid, counter + 1);
self.stack.push(element);
}
}
// Handles the request to delete middle element of stack
func deleteMiddle()
{
if (self.stack.isEmpty() == false)
{
// Get middle element location
let mid: Int = self.stack.size / 2;
self.removeMiddle(mid, 0);
}
else
{
print("\n Stack Is Empty ");
}
}
}
func main()
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
print("\n Stack element ");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
print("\n After Delete stack ");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
print("\n After Delete stack ");
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
print("\n After Delete stack ");
}
main();``````

#### Output

`````` Stack element
1    2    3    4    5    6    7

Delete middle element :  4
After Delete stack
1    2    3    5    6    7

Delete middle element :  5
After Delete stack
1    2    3    6    7

Delete middle element :  3
After Delete stack
1    2    6    7``````
``````/*
Kotlin Program
Delete middle element of a stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, next: StackNode ? )
{
this.element = element;
this.next = next;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size>0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size>0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
fun peek(): Int
{
return this.top!!.element;
}
}
class DeleteElement
{
var stack: MyStack;
constructor()
{
this.stack = MyStack();
}
// Print element of stack
fun printData(): Unit
{
var temp: StackNode? = this.stack.top;
while (temp != null)
{
// Display element value
print("   " + temp.element);
temp = temp.next;
}
print("\n");
}
// Remove middle element of stack
fun removeMiddle(mid: Int, counter: Int): Unit
{
if (counter == mid)
{
// When get middle element
print("\n Delete middle element : " + this.stack.peek());
// Delete middle node
this.stack.pop();
}
else
if (counter<mid && this.stack.isEmpty() == false)
{
// When stack not empty and counter is less than middle position
// Get top element
var element: Int = this.stack.peek();
// Remove top element
this.stack.pop();
// Recursively finding the middle element
this.removeMiddle(mid, counter + 1);
this.stack.push(element);
}
}
// Handles the request to delete middle element of stack
fun deleteMiddle(): Unit
{
if (this.stack.isEmpty() == false)
{
// Get middle element location
var mid: Int = this.stack.size / 2;
this.removeMiddle(mid, 0);
}
else
{
print("\n Stack Is Empty \n");
}
}
}
fun main(args: Array<String>): Unit
{
/*
Created Stack
============

1 <- Top
2
3
4
5
6
7
*/
print("\n Stack element \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
5
6
7
*/
print("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
3
6
7
*/
print("\n After Delete stack \n");
// delete operation
/*
After delete middle element
============
1 <- Top
2
6
7
*/
print("\n After Delete stack \n");
}``````

#### Output

`````` Stack element
1   2   3   4   5   6   7

Delete middle element : 4
After Delete stack
1   2   3   5   6   7

Delete middle element : 5
After Delete stack
1   2   3   6   7

Delete middle element : 3
After Delete stack
1   2   6   7``````

## Time Complexity Analysis

The time complexity of deleting the middle element from the stack using recursion is O(n), where n is the number of elements in the stack. This is because, in the worst case, we may have to remove n/2 elements to reach the middle position, and each removal operation takes constant time. Therefore, the overall time complexity is O(n).

## Output Explanation

The output shows the elements in the stack after deleting the middle elements one by one. The elements are displayed in the reverse order, as it is a stack (LIFO). For example, `1 2 3 6 7` represents the stack `[1, 2, 3, 6, 7]` after deleting the middle elements. After deleting all the middle elements, the stack becomes empty, and the output shows an empty stack.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.