package com.my.suanfa;

import java.util.Stack;

/*
 * 用一个栈实现另一个栈的排序
 * 实现栈中元素从栈顶到栈底依次递减
 * */
public class SortStack {
	public static void sortStackByStack(Stack<Integer> stack) {
		//申请一个辅助栈
		Stack<Integer> help = new Stack<Integer>();
		/*help中元素从顶到底应为依次递增
		 * 如果辅助栈不为空，并且辅助栈栈顶的元素小于cur中保存的元素，
		 * 则表明cur应该在辅助栈栈顶元素的下面，则将help栈顶元素弹出并
		 * 压入stack,直到help栈顶元素大于cur
		 * */
		while(!stack.isEmpty()) {
			//声明一个变量来保存从stack栈中弹出的元素
			int cur = stack.pop();
			while(!help.isEmpty() && help.peek() < cur) {
				stack.push(help.pop());
			}
			//如果help为空，或者help栈顶元素大于cur,则直接将cur压入
			help.push(cur);
		}
		//排序完成后，将help中元素全部压入stack
		while(!help.isEmpty()) {
			stack.push(help.pop());
		}
	}
}