#ctci

SortAStack.java

// There are only a few known sorting algorithm and it is likely that we are facing a variation here.
// Let's look at these algorithms: merge sort, quick sort, insertion sort, bubble sort...
// Since we are only allowed to use one additional stack, we can rule out the first two.
// merge sort requires two additional data structures to merge to one (need 3?)
// quick sort does not seem to apply here since we need to hold the index and it seems hard to keep track of it.
// 
// What about insertion sort? Think about the pop/push and move/insert actions. They seem very similar! When we 
// are moving big numbers to insert a smaller number, it is similar to pop big numbers to another stack and then
// push the smaller number to this stack and then move the bigger numbers back. 
// 
// We can work from this idea and work out the details.

import java.util.Stack;

public class SortAStack {
	public Stack<Integer> sortAStack(Stack<Integer> s1) {
		Stack<Integer> s2 = new Stack<Integer>();

		while (!s1.isEmpty()) {
			int tmp = s1.pop();

			while (!s2.isEmpty() && tmp < s2.peek())
				s1.push(s2.pop());

			s2.push(tmp);
		}
		return s2;
	}

	private static void printStack(Stack<Integer> s) {
		System.out.println("the stack from top to bottom is: ");
		StringBuilder builder = new StringBuilder();
		while (!s.isEmpty()) {
			builder.append(s.pop());
		}
		System.out.println(builder.toString());
	}

	public static void main(String[] args) {
		SortAStack sas = new SortAStack();
		Stack<Integer> s1 = new Stack<Integer>();
		s1.push(3);
		s1.push(1);
		s1.push(2);
		s1.push(4);
		s1.push(0);
		s1.push(5);

		printStack((Stack<Integer>) s1.clone());
		s1 = sas.sortAStack(s1);
		printStack(s1);
	}

}