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.

CC150-3.6.java

package POJ;


import java.util.Random;
import java.util.Stack;


public class Main{

	/**
	 * 
	 *  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.
	 *  
	 *  Solution:
	 *  与书上一样
	 *  
	 *  @Runtime & spaces
	 * 	runtime: O(n^2)
	 * 	space: O(n)
	 * 
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Random d=new Random();
		Stack<Integer> stack=new Stack<Integer>();
		for(int i=0;i<10;i++)
			stack.push(d.nextInt(10));
		sort(stack);
		while(!stack.isEmpty())
			System.out.println(stack.pop());
	}

	public static void sort(Stack<Integer> stack) {
		Stack<Integer> tempStack = new Stack<Integer>();
		while (!stack.isEmpty()) {
			int count = 0;
			int temp = stack.pop();
			// move all elements in temp stack which is smaller than
			// the value (from temp to original stack)
			while (!tempStack.isEmpty() && tempStack.peek() < temp) {
				stack.push(tempStack.pop());
				count++;
			}
			// push the new value
			tempStack.push(temp);
			// push bakc the poped elements
			while (count > 0) {
				tempStack.push(stack.pop());
				count--;
			}
		}
		while (!tempStack.isEmpty()) {
			stack.push(tempStack.pop());
		}
	}
}