CC_3_6

StackSort.java

// Cracking the Coding Interview
// 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.

import java.util.Stack;
class StackSort {
	public static void sortStack(Stack<Integer> s) {
		if (s.isEmpty()) return;
		Stack<Integer> helper = new Stack<Integer>();
		int n = 1;
		while (sortFirstNElement(s, helper, n++)) {};
	}
	// assuming first N-1 elements are sorted, sort the first N elements
	private static boolean sortFirstNElement(Stack<Integer> s, Stack<Integer> helper, int n) {
		int i = 0;
		while(i < n) {
			if (s.isEmpty()) {
				while(!helper.isEmpty()) {
					s.push(helper.pop());
				}
				return false;
			}
			helper.push(s.pop());
			i++;
		}
		int newElement = helper.pop();
		boolean inserted = false;
		while(!helper.isEmpty()) {
			int tmp = helper.peek();
			if (inserted) {
				s.push(helper.pop());
			} else {
				if (tmp < newElement) {
					s.push(helper.pop());
				} else {
					s.push(newElement);
					inserted = true;
				} 
			}
		}
		if (!inserted) {
			s.push(newElement);
		}
		return true;
	}


	public static void main(String[] args) {
		Stack<Integer> s = new Stack<Integer>();
		sortStack(s);
		assert s.isEmpty();
		s.push(1);
		sortStack(s);
		assert s.pop() == 1;
		assert s.isEmpty();

		s.push(3);
		s.push(2);
		s.push(2);
		s.push(1);

		sortStack(s);
		assert s.pop() == 3;
		assert s.pop() == 2;
		assert s.pop() == 2;
		assert s.pop() == 1;
		assert s.isEmpty();

		System.out.println("Tests Passed");

	}
}