TwoStackSort

cc150
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
测试样例：

[1,2,3,4,5]

返回：

[5,4,3,2,1]

代码

package _09_Linear.Stack_QueuePractice;

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

public class TwoStackSort {
    public static void main(String[] args) {
        int[] arr = {80, 2, 3, 14, 5, 19, 4, 70};
        ArrayList<Integer> res = new TwoStackSort().twoStackSort(arr);
        for (int a : res) {
            System.out.println(a);
        }
    }

    public ArrayList<Integer> twoStackSort(int[] number) {
        // 初始化原始栈
        Stack<Integer> source = new Stack<>();

        for (int i = 0; i < number.length; i++) {
            source.push(number[i]);
        }
        Stack<Integer> target = twoStackSort(source);

        ArrayList<Integer> list = new ArrayList<>();

        while (!target.empty()) {
            list.add(target.pop());//从栈顶取出 从大大小 --> list
        }
        return list;

    }

    public Stack<Integer> twoStackSort(Stack<Integer> source) {
        Stack<Integer> target = new Stack<>();
        while (!source.empty()) {
            int v1 = source.pop();//揭开 盖子
            if (target.empty()) {
                target.push(v1);
            } else {//比较
                if (v1 >= target.peek())//比盖子大 就 压进去 大的在栈顶
                    target.push(v1);
                else {
                    while (!target.empty() && v1 < target.peek()) {//逆序 装回去
                        source.push(target.pop());
                    }
                    target.push(v1);
                }
            }
        }
        return target;
    }
}