Delete Middle Element From Stack in Java
In this problem, we take a stack input from the user and Delete the middle of the stack and return the original stack without the middle element
Example 1:
Input: Stack: [1,23,12,17,50]
Output: After deleting middle element from the stack: [1,23,17,50]
Explanation: We Iterate the stack and find the middle element and delete the element and return the stack without the middle element.
Example 2:
Input: Stack: []
Output: The Stack has no elements
Two Pointer Approach
Here we use two pointers one is slow pointer and another is fast pointer and both pointer start from intial position of stack and then slow pointer moves 1 step for 1 iteration where as fast pointer moves 2 steps for 1 iteration. When fast pointer reaches the end the slow will be in the middle of the stack. Then pop the slow pointer element.
FileName: DeleteMiddleElementFromStack.java
import java.util.Stack;
public class DeleteMiddleElementFromStack {
public static void deleteMiddleElement(Stack<Integer> stack) {
if (stack.isEmpty()) {
return; // Nothing to delete if stack is empty
}
Stack<Integer> removedElements = new Stack<>();
Stack<Integer> tempStack = new Stack<>();
// Initialize slow and fast pointers
Stack<Integer> slowPointer = stack;
Stack<Integer> fastPointer = stack;
// Move fast pointer two steps at a time and slow pointer one step at a time
while (fastPointer.size() > 1 && fastPointer.size() != 0) {
removedElements.push(slowPointer.pop());
fastPointer.pop();
if (!fastPointer.isEmpty()) {
fastPointer.pop();
}
tempStack.push(removedElements.pop());
}
if (!slowPointer.isEmpty()) {
slowPointer.pop();
}
// Push back removed elements into the stack
while (!tempStack.isEmpty()) {
stack.push(tempStack.pop());
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(5);
stack.push(8);
stack.push(3);
stack.push(2);
stack.push(7);
System.out.println("Stack before deleting middle element: " + stack);
deleteMiddleElement(stack);
System.out.println("Stack after deleting middle element: " + stack);
}
}
Output:
Stack before deleting middle element: [5, 8, 3, 2, 7]
Stack after deleting middle element: [5, 8, 2, 7]
Complexity Analaysis:
Time Complexity: n is the number of elements on the stack, and it takes O(n) time to traverse the stack using two pointers. O(n) time is also required to remove the middle element from the stack since we might have to pop and push elements.
Hence, O(n) is the code's total time complexity.
Space Complexity: Two more stacks are used, one for storing elements during traversal and the other for temporarily storing discarded elements. Auxiliary stacks and other ongoing space utilization cause the space complexity to be O(n).
Two Stacks Approach
In Java, there is a approach for removing the center element from a stack called the Two Stacks Approach. In this method uses two different stacks to handle the original stack's components. The approach fundamental idea is to divide the original stack into two sections, one with components that comes before the middle element and the other with elements that comes after it, all while maintaining the original order of the other items.
FileName: DeleteMiddleElementFromStack.java
import java.util.Stack;
public class DeleteMiddleElementFromStack {
public static void deleteMiddleElement(Stack<Integer> stack) {
if (stack.isEmpty()) {
return; // Nothing to delete if stack is empty
}
Stack<Integer> tempStack = new Stack<>();
Stack<Integer> removedElements = new Stack<>();
// Push elements from original stack to tempStack until reaching the middle element
while (stack.size() > 1) {
tempStack.push(stack.pop());
}
stack.pop();
// Pop elements from tempStack back to original stack, skipping the removed middle element
while (!tempStack.isEmpty()) {
removedElements.push(tempStack.pop());
}
while (!removedElements.isEmpty()) {
stack.push(removedElements.pop());
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(5);
stack.push(8);
stack.push(3);
stack.push(2);
stack.push(7);
System.out.println("Stack before deleting middle element: " + stack);
deleteMiddleElement(stack);
System.out.println("Stack after deleting middle element: " + stack);
}
}
Output:
Stack before deleting middle element: [5, 8, 3, 2, 7]
Stack after deleting middle element: [5, 8, 2, 7]
Complexity Analaysis:
Time Complexity: O(n), where n is the number of elements in the stack, is required to traverse the initial stack in order to get to the middle element. It takes O(n) in total to push and pop elements between stacks because each element must be moved up to the middle. As a result, the code's overall time complexity is O(n).
Space Complexity: We employ two more stacks, one for storing components that have been removed and one for momentarily storing elements that come before the middle element. These stacks have an O(n) space complexity since they have the capacity to hold every element in the original stack. As a result, the code's overall space complexity is O(n).
Recursion Approach
we create a recursive function that goes through the stack and eliminates the middle element whenever it's found. When the stack is empty or has only one element, the recursion's base case occurs, meaning there isn't a middle element to eliminate. Recursion is the process of taking elements out of the stack one after the other till we get to the center element. After the center piece has been located, the stack contains it no more. Until the base case is reached, the recursion then keeps eliminating the remaining elements from the stack.
FileName: DeleteMiddleElementFromStack.java
import java.util.Stack;
public class DeleteMiddleElementFromStack {
public static void deleteMiddleElement(Stack<Integer> stack) {
if (stack.isEmpty()) {
return; // Base case: stack is empty
}
int size = stack.size();
int middle = size / 2;
// Recursive helper function to delete middle element
deleteMiddleElementHelper(stack, middle, 0);
}
private static void deleteMiddleElementHelper(Stack<Integer> stack, int middle, int index) {
if (index == middle) {
stack.pop();
return;
}
int topElement = stack.pop();
deleteMiddleElementHelper(stack, middle, index + 1);
stack.push(topElement); // Push the top element back after recursion
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(5);
stack.push(8);
stack.push(3);
stack.push(2);
stack.push(7);
System.out.println("Stack before deleting middle element: " + stack);
deleteMiddleElement(stack);
System.out.println("Stack after deleting middle element: " + stack);
}
}
Output:
Stack before deleting middle element: [5, 8, 3, 2, 7]
Stack after deleting middle element: [5, 8, 2, 7]
Complexity Analaysis:
Time Complexity: O(n), where n is the number of elements in the stack, is the temporal complexity of the recursion. So that the middle element may be reached by the recursion, which requires going through each element of the stack once.
Space Complexity: Because of the recursive calls, the space complexity is O(n). Memory on the call stack is used by each recursive call. The space complexity is linear in relation to the number of elements in the stack since there can be a maximum of n recursive calls (one for each member in the stack).