用一个栈实现另一个栈的排序

题目

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

分析

通过辅助栈s来完成排序，数据栈data进行pop操作得到的数字记为current。

若current小于s.peek()，则直接放入s，

否则将将s中的元素逐一压入data，直到找到大于current的栈顶元素，将current放入s。

重复上面的动作直到data为空，此时s中的元素从栈顶到栈底已经按照从小到大的顺序排好了，再讲s逐个放入data即可。

public class Solution {
    public void sort(Stack<Integer> data) {
        Stack<Integer> s = new Stack<>();
        int current;
        while (!data.isEmpty()) {
            current = data.pop();
            add(s, data, current);
        }
        while (!s.isEmpty()) {
            data.push(s.pop());
        }
    }

    public void add(Stack<Integer> s, Stack<Integer> data, int current) {
        while (!s.isEmpty() && s.peek() < current) {
            data.push(s.pop());
        }
        s.push(current);
    }
}