给定一个乱序的栈，设计算法将其升序排列。

ps: 允许额外使用一个栈来辅助操作

输入 [4, 2, 1, 3] 输出 [1, 2, 3, 4]

递增栈+原栈+临时变量

遇到原栈中的递减子序列，直接弹出存到临时栈中，此时临时栈中是递增的。 遇到原栈中的递增子序列，即此时临时栈中的元素大于原栈的栈顶元素，要利用临时变量保存小元素， 把临时栈中的那个大元素再放回原栈栈顶，然后把临时变量的值放到临时栈栈顶，然后把原栈栈顶的元素放到临时栈栈顶。本质上就是交换两个元素。

维护辅助栈为单调递增栈。

经过若干次“倒腾”，便可将所有元素存至辅助栈。

由于每次“倒腾”，辅助栈都是有序的，因此最终的辅助栈就是我们要的结果。

public class Solution {
    public static Deque<Integer> stackSort(Deque<Integer> stk) {
        Deque<Integer> tmp = new ArrayDeque<>(); // 临时栈，用于辅助排序

        while (!stk.isEmpty()) { // 当输入栈不为空时继续循环
            int peak = stk.pop(); // 临时存储输入栈的栈顶元素

            // 如果输入栈栈顶元素小于临时栈栈顶元素，就把临时栈中大于输入栈栈顶元素的元素弹出并压回输入栈
            while (!tmp.isEmpty() && tmp.peek() > peak) {
                stk.push(tmp.pop());
            }
            // 将当前元素压入临时栈
            tmp.push(peak);
        }

        return tmp; // 返回排序后的栈
    }
}

• 时间复杂度：O(n²)。在最坏情况下，每个元素可能需要与临时栈中的所有元素进行比较和移动，导致二次方级别的操作次数。
• 空间复杂度：O(n)。使用了一个额外的临时栈 tmp 来辅助排序，所需空间与输入栈的大小成线性关系。