Delete middle element of a stack

Given a stack with push(), pop(), and empty() operations, The task is to delete the middle element of it without using any additional data structure.

Input: s = [10, 20, 30, 40, 50]
Output: [50, 40, 20, 10]
Explanation: The bottom-most element will be 10 and the top-most element will be 50. Middle element will be element at index 3 from bottom, which is 30. Deleting 30, stack will look like [10, 20, 40, 50].

Input: s = [5, 8, 6, 7, 6, 6, 5, 10, 12, 9]
Output: [9, 12, 10, 5, 6, 7, 6, 8, 5]

Approach - Using Vector - O(n) Time and O(n) Space

The idea for this approach is that we just put all the elements of stack into a vector, then traverse over the vector and push the elements back into stack, ignoring the mid element for even (n/2) and for odd (ceil(n/2)).

#include <iostream> #include <stack> #include <vector> using namespace std; void deleteMid(stack<int>& st, int size) {  // Use a vector to store stack elements  vector<int> v;  while(!st.empty()) {  v.push_back(st.top());  st.pop();  }  // Find the middle index  int mid = size / 2;  // Remove the middle element  v.erase(v.begin() + mid);  // Push elements back to the stack  for(int i = v.size() - 1; i >= 0; i--) {  st.push(v[i]);  } } int main() {  stack<int> st;  st.push(10);  st.push(20);  st.push(30);  st.push(40);  st.push(50);  int size = st.size();  deleteMid(st, size);  while (!st.empty()) {  int p = st.top();  st.pop();  cout << p << " ";  }    return 0; } 

import java.util.*; public class GfG {  public static void deleteMid(Stack<Integer> st, int size) {  // Use an ArrayList to store stack elements  ArrayList<Integer> v = new ArrayList<>();  while (!st.isEmpty()) {  v.add(st.pop());  }  // Find the middle index  int mid = size / 2;  // Remove the middle element  v.remove(mid);  // Push elements back to the stack  for (int i = v.size() - 1; i >= 0; i--) {  st.push(v.get(i));  }  }  public static void main(String[] args) {  Stack<Integer> st = new Stack<>();  st.push(10);  st.push(20);  st.push(30);  st.push(40);  st.push(50);  int size = st.size();  deleteMid(st, size);  while (!st.isEmpty()) {  int p = st.pop();  System.out.print(p + " ");  }  } } 

from collections import deque def delete_mid(st): # Use a list to store stack elements v = [] while st: v.append(st.pop()) # Find the middle index mid = len(v) // 2 # Remove the middle element v.pop(mid) # Push elements back to the stack for i in range(len(v) - 1, -1, -1): st.append(v[i]) if __name__ == '__main__': st = deque() st.append(10) st.append(20) st.append(30) st.append(40) st.append(50) delete_mid(st) while st: print(st.pop(), end=' ') 

using System; using System.Collections.Generic; class GfG {  public static void DeleteMid(Stack<int> st, int size) {  // Use a list to store stack elements  List<int> v = new List<int>();  while (st.Count > 0) {  v.Add(st.Pop());  }  // Find the middle index  int mid = size / 2;  // Remove the middle element  v.RemoveAt(mid);  // Push elements back to the stack  for (int i = v.Count - 1; i >= 0; i--) {  st.Push(v[i]);  }  }  static void Main() {  Stack<int> st = new Stack<int>();  st.Push(10);  st.Push(20);  st.Push(30);  st.Push(40);  st.Push(50);  int size = st.Count;  DeleteMid(st, size);  while (st.Count > 0) {  Console.Write(st.Pop() + " ");  }  } } 

function deleteMid(st) {  let v = [];  while (st.length > 0) {  v.push(st.pop());  }  let mid = Math.floor(v.length / 2);  v.splice(mid, 1);  for (let i = v.length - 1; i >= 0; i--) {  st.push(v[i]);  } } const st = [10, 20, 30, 40, 50]; deleteMid(st); let result = ''; while (st.length > 0) {  result += st.pop() + ' '; } console.log(result.trim()); 

50 40 20 10 

[Expected Approach 1] - Using Recursion - O(n) Time and O(n) Space

Remove elements of the stack recursively until the count of removed elements becomes half the initial size of the stack, now the top element is the middle element thus pop it and push the previously removed elements in the reverse order.  

Follow the steps below to implement the idea:

• Store the stack size in a variable sizeofstack and a variable current to track the current size of stack.
• Recursively pop out the elements of the stack
  • Pop the element from the stack and increment current by one then recur for the remaining stack.
  • The base case would be when the current becomes equal to sizeofstack / 2 then pop the top element.
  • Push the element that was popped before the recursive call. 

#include <iostream> #include <stack> using namespace std; void deleteMid_util(stack<int>& st, int sizeOfStack, int current) {  if(current == sizeOfStack / 2)  {  st.pop();  return;  }  int x = st.top();  st.pop();  current += 1;  deleteMid_util(st, sizeOfStack, current);  st.push(x); } void deleteMid(stack<int>& st, int sizeOfStack) {  deleteMid_util(st, sizeOfStack, 0); } int main() {  stack<int> st;  st.push(10);  st.push(20);  st.push(30);  st.push(40);  st.push(50);  deleteMid(st, st.size());  while (!st.empty())  {  int p = st.top();  st.pop();  cout << p << " ";  }  return 0; } 

import java.util.Stack; public class GfG {  static void deleteMidUtil(Stack<Integer> st, int sizeOfStack, int current) {  if (current == sizeOfStack / 2) {  st.pop();  return;  }  int x = st.pop();  current += 1;  deleteMidUtil(st, sizeOfStack, current);  st.push(x);  }  static void deleteMid(Stack<Integer> st, int sizeOfStack) {  deleteMidUtil(st, sizeOfStack, 0);  }  public static void main(String[] args) {  Stack<Integer> st = new Stack<>();  st.push(10);  st.push(20);  st.push(30);  st.push(40);  st.push(50);  deleteMid(st, st.size());  while (!st.isEmpty()) {  int p = st.pop();  System.out.print(p + " ");  }  } } 

class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() if not self.is_empty() else None def top(self): return self.items[-1] if not self.is_empty() else None def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items) def delete_mid_util(st, sizeOfStack, current): if current == sizeOfStack // 2: st.pop() return x = st.pop() current += 1 delete_mid_util(st, sizeOfStack, current) st.push(x) def delete_mid(st): delete_mid_util(st, st.size(), 0) if __name__ == '__main__': st = Stack() st.push(10) st.push(20) st.push(30) st.push(40) st.push(50) delete_mid(st) while not st.is_empty(): p = st.pop() print(p, end=' ') 

using System; using System.Collections.Generic; class GfG {  static void DeleteMidUtil(Stack<int> st, int sizeOfStack, int current)  {  if (current == sizeOfStack / 2)  {  st.Pop();  return;  }  int x = st.Pop();  current += 1;  DeleteMidUtil(st, sizeOfStack, current);  st.Push(x);  }  static void DeleteMid(Stack<int> st)  {  DeleteMidUtil(st, st.Count, 0);  }  static void Main()  {  Stack<int> st = new Stack<int>();  st.Push(10);  st.Push(20);  st.Push(30);  st.Push(40);  st.Push(50);  DeleteMid(st);  while (st.Count > 0)  {  int p = st.Pop();  Console.Write(p + " ");  }  } } 

function deleteMidUtil(st, sizeOfStack, current) {  if (current === Math.floor(sizeOfStack / 2)) {  st.pop();  return;  }  let x = st.pop();  current += 1;  deleteMidUtil(st, sizeOfStack, current);  st.push(x); } function deleteMid(st) {  deleteMidUtil(st, st.length, 0); } let st = []; st.push(10); st.push(20); st.push(30); st.push(40); st.push(50); deleteMid(st); while (st.length > 0) {  let p = st.pop();  process.stdout.write(p + ' '); } 

50 40 20 10 

[Expected Approach 2] - Using Stack - O(n) Time and O(n) Space

Pop the elements above the middle element of the given stack and use a temp stack to store these popped elements. Then pop the middle element and push the elements of the temp stack in the given stack.

Follow the below steps to implement the idea:

• Initialize an empty stack temp and a variable count with 0.
• Run a while loop till count becomes equal to half the initial size of the given stack 
  • Pop the element of the given stack and push them in temp.
• Pop the top element from the given stack.
• Run a while loop till temp becomes empty. 
  • Push the element of temp and push them in the given stack.

#include <iostream> #include <stack> using namespace std; void deleteMid(stack<int>& st) {  int n = st.size();  stack<int> tempSt;  int count = 0;  while (count < n / 2) {  int c = st.top();  st.pop();  tempSt.push(c);  count++;  }  st.pop();  while (!tempSt.empty()) {  st.push(tempSt.top());  tempSt.pop();  } } int main() {  stack<int> st;  st.push(10);  st.push(20);  st.push(30);  st.push(40);  st.push(50);  deleteMid(st);  while (!st.empty()) {  int p = st.top();  st.pop();  cout << p << " ";  }  return 0; } 

import java.util.Stack; public class GfG {  public static void deleteMid(Stack<Integer> st) {  int n = st.size();  Stack<Integer> tempSt = new Stack<>();  int count = 0;  while (count < n / 2) {  int c = st.pop();  tempSt.push(c);  count++;  }  st.pop();  while (!tempSt.isEmpty()) {  st.push(tempSt.pop());  }  }  public static void main(String[] args) {  Stack<Integer> st = new Stack<>();  st.push(10);  st.push(20);  st.push(30);  st.push(40);  st.push(50);  deleteMid(st);  while (!st.isEmpty()) {  int p = st.pop();  System.out.print(p + " ");  }  } } 

def delete_mid(st): n = len(st) temp_st = [] count = 0 while count < n // 2: c = st.pop() temp_st.append(c) count += 1 st.pop() while temp_st: st.append(temp_st.pop()) if __name__ == '__main__': st = [] st.append(10) st.append(20) st.append(30) st.append(40) st.append(50) delete_mid(st) while st: p = st.pop() print(p, end=' ') 

using System; using System.Collections.Generic; class GfG {  static void DeleteMid(Stack<int> st) {  int n = st.Count;  Stack<int> tempSt = new Stack<int>();  int count = 0;  while (count < n / 2) {  int c = st.Pop();  tempSt.Push(c);  count++;  }  st.Pop();  while (tempSt.Count > 0) {  st.Push(tempSt.Pop());  }  }  static void Main() {  Stack<int> st = new Stack<int>();  st.Push(10);  st.Push(20);  st.Push(30);  st.Push(40);  st.Push(50);  DeleteMid(st);  while (st.Count > 0) {  int p = st.Pop();  Console.Write(p + " ");  }  } } 

function deleteMid(st) {  const n = st.length;  const tempSt = [];  let count = 0;  while (count < Math.floor(n / 2)) {  const c = st.pop();  tempSt.push(c);  count++;  }  st.pop();  while (tempSt.length > 0) {  st.push(tempSt.pop());  } } const st = []; st.push(10); st.push(20); st.push(30); st.push(40); st.push(50); deleteMid(st); while (st.length > 0) {  const p = st.pop();  process.stdout.write(p + ' '); } 

50 40 20 10