# 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)
