# 1. 用给一个辅助栈来实现另一个栈的排序
需要将待排序栈实现栈顶到栈底的大小顺序为从大到小。
分析，假设待排序栈为`A`，辅助栈为`B`，那么：
- 结果`B`的顺序为栈顶到栈底的大小顺序为从大到小，那么`B`每次压入栈的数为每次的最小值；
- 由于栈是一种限定在栈顶删除或者插入的数据结构，所以`B`中压入的最小值应该来源于`A`的栈顶。也就是说辅助栈`A`用来存储每次的最小值；
- 也就是说，在辅助栈`A`中最终存储的应该是栈顶到栈底的大小顺序为从小到大；
那么，如果我们需要做到辅助栈的栈内元素栈顶到栈底的大小顺序为从小到大，我们需要进行当前从`B`栈出栈元素和辅助栈的大小关系，然后进行交换保证有序，交换中就需要使用待排序栈的反复入栈和出栈。有点类似于临时空间交换，所以我们还需要一个临时变脸来存储当前值。比如下面的案例：
- `A`出栈，赋值到`cur`，由于辅助栈`B`为空，故而没有比较交换对象，直接插入到辅助栈`B`即可。
- `A`出栈，赋值到`cur=5`，由于要保证辅助栈`B`从栈顶到栈顶为小到大，而此时栈中为`3`，如果压入`cur`，不满足规则，故而需要将小于`cur=5`的数据都移除辅助栈`B`，然后再将`cur=5`入栈`B`。
此时的栈示意图为：
那么不妨继续上述操作：
- `A`出栈，赋值到`cur=3`，如果将当前`cur`压入辅助栈`B`，满足栈顶到栈顶为小到大的规则，故而直接压入栈；
继续，`A`出栈，赋值到`cur=6`，现在辅助栈`B`中的所有元素都不满足条件，所以需要将元素依次移除，然后再将`cur`压入栈`B`，即：
重复上述流程，可以写出如下代码：
~~~
/**
* 使用一个栈来实现另一个栈的排序
* 2021-12-30
* @param stack 待排序栈
*/
public void sortStackByStack(Stack<Integer> stack){
Stack<Integer> help = new Stack<Integer>();
while(!stack.isEmpty()){
int cur = stack.pop();
while(!help.isEmpty() && cur > help.peek()){
stack.push(help.pop());
}
help.push(cur);
}
while(!help.isEmpty()){
stack.push(help.pop());
}
}
~~~
更加直观的过程可以查看下面的动画：
[stack/Video\_2022-01-03\_094846.wmv · weizu\_cool/GifSource - 码云 - 开源中国 (gitee.com)](https://gitee.com/weizu_cool/gif-source/blob/master/stack/Video_2022-01-03_094846.wmv)
