Stack_Queue 把栈排序 Sort a stack @CareerCup

原文：

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

译文：

写程序将一个栈按升序排序。对这个栈是如何实现的，你不应该做任何特殊的假设。 程序中能用到的栈操作有：push | pop | peek | isEmpty。

至少有四种方法：

1）借助另一个栈来排序：

另一个栈（有序栈）装排序完（从大到小）的结果。如何把无序栈的元素添加到有序栈呢？我们可以把下一个待插入的元素存放在一个临时变量toInsert里，然后在有序栈里，把所有比toInsert大的都倒腾到无序栈内。这样保证当toInsert插入有序栈时，toInsert以下的所有元素都小于它。然后继续处理下一个无序栈栈顶元素，最后直到无序栈中的所有元素都被转移到有序栈中！Time: O(N^2), Space: O(N)

2）如果可以用heap/priority queue，则就太简单了。

3） 可以在栈上进行merge sort。把当前栈的元素分到左右两个子栈，然后分别对两个子栈排序。最后是merge过程。不过要注意：栈只能从栈顶取元素，而左右栈已经是按从大到小排序好，所以要取出较大的元素压入stack，这样stack会变成从小到大排序，因此在merge的最后需要reverse stack！

4） 还可以在栈上进行quick sort。原理同merge sort

package Stack_Queue;

import java.util.Stack;

import CtCILibrary.AssortedMethods;

public class S3_6 {

	// 输入一个乱序的栈，返回一个排序过（栈顶最大，栈底最小）的栈
	// Time: O(N^2), Space: O(N)
	public static Stack<Integer> sort(Stack<Integer> stack) {
		Stack<Integer> sorted = new Stack<Integer>();
		while( !stack.isEmpty() ) {
			int toInsert = stack.pop();		// 先保存待处理的元素到一个临时变量
			while( !sorted.isEmpty() && sorted.peek() > toInsert ) {		// 把比toInsert大的元素都倒腾到stack
				stack.push(sorted.pop());
			}
			sorted.push(toInsert);			// 现在sorted栈顶元素已经小于toInsert，可以直接插入了
		}
		return sorted;
	}
	
	// mergeSort
	// Time: O(NlogN), Space: O(N)
	public static Stack<Integer> mergeSort(Stack<Integer> stack) {
		if ( stack.size() <= 1) {
			return stack;
		}
		
		Stack<Integer> left = new Stack<Integer>();
		Stack<Integer> right = new Stack<Integer>();
		
		int count = 0;
		while (stack.size() != 0) {
			count++;
			if (count % 2 == 0) {
				left.push(stack.pop());
			} else {
				right.push(stack.pop());
			}
		}
		
		left = mergeSort(left);
		right = mergeSort(right);
		
		// merge合并过程
		while ( left.size()>0 || right.size()>0 ) {
			if ( left.size() == 0 ) {	// 左栈为空，把右栈全部添加到stack
				stack.push(right.pop());
			} else if ( right.size() == 0 ) {	// 右栈为空为空，把左栈全部添加到stack
				stack.push( left.pop() );
			} 
			// 注意到栈只能从栈顶取元素，而左右栈已经是按从大到小排序好
			// 所以要取出较大的元素压入stack，这样stack会变成从小到大排序，
			// 因此在merge的最后需要reverse stack
			else if ( right.peek().compareTo(left.peek()) <= 0 ) {
				stack.push(left.pop());
			} else {
				stack.push(right.pop());
			}
		}
		
		Stack<Integer> reveseStack = new Stack<Integer>();
		while (stack.size() > 0 ) {
			reveseStack.push(stack.pop());
		}
		
		return reveseStack;
	}
	
	
	public static void main(String [] args) {
		Stack<Integer> s = new Stack<Integer>();
		
		for (int k = 1; k < 5; k++) {
				int r = AssortedMethods.randomIntInRange(0,  1000);
				s.push(r);
		}
		
//		s = sort(s);
		s = mergeSort(s);
		int last = Integer.MAX_VALUE;
		while(!s.isEmpty()) {
			int curr = s.pop();
			System.out.println(curr);
			if (curr > last) {
				System.out.println("Error: " + last + " " + curr);
			}
			last = curr;
		}
	}
}