package org.wesome.dsalgo;
import java.util.Stack;
public class SortStack {
public static Stack<Integer> sortStack(Stack<Integer> unsortedStack) {
System.out.println("unsorted stack is = " + unsortedStack);
Stack<Integer> sortedStack = new Stack<>();
// we will return sortedStack so loop while unsortedStack is not empty.
while (!unsortedStack.isEmpty()) {
// pop out the first element from main stack
int unsortedStackTop = unsortedStack.pop();
System.out.println("removing unsortedStackTop is = " + unsortedStackTop + " unsortedStackTop is = " + unsortedStack);
// if temporary stack has data and unsortedStack top is greater than sortedStack top
while (!sortedStack.isEmpty() && sortedStack.peek() > unsortedStackTop) {
// pop from temporary stack and push it to the unsortedStack stack
System.out.println("sortedStackTop = " + sortedStack.peek() + " greater then unsortedStackTop = " + unsortedStackTop);
System.out.println("so take all the elements of sortedStack which are greater then " + unsortedStackTop + " and put in unSortedStack, then put " + unsortedStackTop + " at the top of sortedStack");
System.out.println("removing sortedStack top = " + sortedStack.peek() + " and putting back into unsortedStack");
unsortedStack.push(sortedStack.pop());
System.out.println("now unsortedStack is = " + unsortedStack);
}
System.out.println("pushing unsortedStackTop top = " + unsortedStackTop + " into sortedStack");
sortedStack.push(unsortedStackTop);
System.out.println("now sortedStack is = " + sortedStack);
System.out.println("now unsortedStack is = " + unsortedStack + "\n");
}
System.out.print("sortedStack is = " + sortedStack);
return sortedStack;
}
}