No data structures except an extra stack can be used to sort our original stack. smallest elements on top.

SortStack.java

//No data structures except an extra stack can be used to sort our original stack. smallest elements on top.
import java.util.Arrays;
import java.util.Stack;

public class SortStack<T extends Comparable> {
	private Stack<T> main, storage;
	private T temp;
	
	public SortStack(Stack<T> s){
		main = s;
		storage = new Stack<>();

	}
	
	//Minimum values at top of stack.
	//constraint: can only use another stack to store vars.
	public void sort(){
		// TODO do checks here to make sure stack is not empty, etc 
		//bottom of storage will be min
		storage.push(main.pop());
		while(!main.isEmpty()){
			this.temp = main.pop();
			//if top of main stack is smaller than the top of our storage stack, we need to reposition 
			if(this.temp.compareTo(storage.peek()) < 0){
				while(!storage.isEmpty() && this.temp.compareTo(storage.peek()) < 0){
					main.push(storage.pop());
				}
				storage.push(this.temp);
			}
			else{
				storage.push(this.temp);
			}
		}
		
		//push everything back to main.
		while(!storage.isEmpty()){
			main.push(storage.pop());
		}
	}
	public String toString(){
		return main.toString();
	}
}