import java.util.ArrayList;
import java.util.Stack;

/*
 * 请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，
 * 但不得将元素复制到别的数据结构中。
 * 给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。
 * 请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
 * 测试样例：
 * [1,2,3,4,5]
 *  返回：[5,4,3,2,1]
 */
public class TwoStacks {
	public ArrayList<Integer> twoStacksSort(int[] numbers) {
		if (numbers == null || numbers.length < 1)
			return null;
		Stack<Integer> myStack1 = new Stack<Integer>();
		Stack<Integer> myStack2 = new Stack<Integer>();
		ArrayList<Integer> myResult = new ArrayList<Integer>();
		for (int i = 0; i < numbers.length; i++) {
			myStack1.push(numbers[i]);
		}
		while (!myStack1.empty()) {
			int myTemp = myStack1.pop();
			while (!myStack2.empty() && myStack2.peek() > myTemp) {
				myStack1.push(myStack2.pop());
			}
			myStack2.push(myTemp);
		}
		while (!myStack2.empty()) {
			myResult.add(myStack2.pop());
		}
		return myResult;
	}

}