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].
Brute Force Approach to Delete Middle Element of Stack.
- 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.
// 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()); } } }
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.
- 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.
// 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); } } }
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.
No comments:
Post a Comment