#CC150 #CC150-chap3 3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array).The stack supports the following operations: push, pop, peek, and isEmpty.

StackSorter.java

//3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array).The stack supports the following operations: push, pop, peek, and isEmpty.

public class StackSorter{
	
	// Variation of Insertion Sort by using an extra stack. Iterate through every item in the input stack
	// We need to find the right place to insert the item in the result stack
	// we need to pop every item that is larger than it and we can store them by pushing them in the input stack, and then we push the element in the result stack
	// Time: O(n^2), Space O(n)
	public static Stack<Integer> sortStackAscWithOneExtraStack(Stack<Integer> s){
		Stack<Integer> r = new Stack<Integer>();
		while(!s.empty()){
			// Take each element out, store in a temporaty variable
			int tmp = s.pop();
			// Insert the element in the right place in the result stack
			// pop the larger items and store them in the original stack
			while(!r.empty() && r.peek()>tmp){
				s.push(r.pop());
			}
			// insert the tmp element to the result stack, it is the largest in the result stack.
			r.push(tmp);
		}
		
		return r;
	}
}