Given a Stack, delete its middle element, while preserving the order of the rest of the elements.
| Input Parameters |
Expected outputs |
Stack nodes:
9 <- 14 <- 17 <- 34 <- 21 <- 28 <-
|
Delete Middle Term, Stack nodes:
9 <- 14 <- 34 <- 21 <- 28 <-
|
Stack nodes:
9 <- 14 <- 17 <- 34 <- 21 <- 28 <- 35 <-
|
Delete Middle Term, Stack nodes:
9 <- 14 <- 17 <- 21 <- 28 <- 35 <-
|
| Find the position of the middle term:
If size of stack is odd, middle term is (stackSize+1)/2.
If size of stack is even, we will consider (stackSize /2) as the middle term.
|
| Create a temporary stack for processing purposes.
|
| For indices 0 to (middle term-2), remove the data from input stack and add to temporary stack.
|
| For index (middle term-1) remove it from input stack.
|
| For all data from temp stack, remove the data from temp stack and add to input stack.
|
| The middle term is deleted and order of stack has been preserved.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.Deque;
import java.util.LinkedList;
import java.util.Iterator;
public class StackDeleteMiddle {
private Deque< Integer > tempStack=null;
public Deque< Integer > deleteMiddle(Deque< Integer > stack) throws Exception{
int n;
if (stack.size() % 2!=0) {
n=(stack.size()+1)/2;
}else {
n=(stack.size())/2;
}
tempStack=new LinkedList<Integer>();
for (int idx=0;idx < n; idx++) {
if (idx != n-1) {
tempStack.offerFirst((int)stack.poll());
}else {
stack.poll();
}
}
while (tempStack.size() !=0) {
stack.offerFirst((int) tempStack.poll());
}
return stack;
}
public static void printStack(Deque<Integer> stack) throws Exception {
System.out.println();
System.out.println("**************************************************************************************************");
System.out.print("Stack nodes: ");
Iterator itr=stack.iterator();
System.out.print("(top of stack)");
while (itr.hasNext()) {
System.out.print(itr.next());
System.out.print(" <- ");
}
System.out.println();
System.out.println("**************************************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
/************************
Test Cases given below:
************************/
try {
Deque stack=new LinkedList();
System.out.print("Add to stack");
stack.add(9);
stack.add(14);
stack.add(17);
stack.add(34);
stack.add(21);
stack.add(28);
printStack(stack);
StackDeleteMiddle stackDeleteMiddle=new StackDeleteMiddle();
System.out.println("Delete Middle Term:");
stack=stackDeleteMiddle.deleteMiddle(stack);
printStack(stack);
stack=new LinkedList();
System.out.print("Add to stack");
stack.add(9);
stack.add(14);
stack.add(17);
stack.add(34);
stack.add(21);
stack.add(28);
stack.add(35);
printStack(stack);
stackDeleteMiddle=new StackDeleteMiddle();
System.out.println("Delete Middle Term:");
stack=stackDeleteMiddle.deleteMiddle(stack);
printStack(stack);
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
}