# 使用臨時堆棧對堆棧進行排序

## 例

`9 4 2 -1 6 20`
`20 9 6 4 2 -1`
`2 1 4 3 6 5`
`6 5 4 3 2 1`

```Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]```

## 使用臨時堆棧對堆棧進行排序的算法

1. 初始化堆棧數據結構，然後將元素插入/推入其中。
2. 之後，創建一個函數sort（），該函數接受一個堆棧作為其參數。 在其中初始化另一個臨時/輔助堆棧tmpStack。
3. 在原始堆棧不為空的情況下遍歷，創建一個變量tmp並將原始堆棧的頂部存儲在其中。 之後，彈出原始堆棧的頂部。
4. 在tmpStack不為空且tmpStack的頂部（即臨時堆棧）大於或等於變量tmp時再次遍歷，將臨時堆棧的頂部推入原始堆棧中，然後彈出臨時堆棧的頂部。
5. 將變量tmp推送到臨時堆棧中。
6. 當臨時堆棧不為空時，將其打印在頂部，然後將其彈出。

## 推薦碼

### C ++程序使用遞歸對堆棧進行排序

```#include <iostream>
#include <stack>
using namespace std;

stack<int> sort(stack<int> &input){
stack<int> tmpStack;

while(!input.empty()){

int tmp = input.top();
input.pop();

while(!tmpStack.empty() && tmpStack.top() > tmp){
input.push(tmpStack.top());
tmpStack.pop();
}

tmpStack.push(tmp);
}

return tmpStack;
}

int main(){
stack<int> input;

input.push(20);
input.push(6);
input.push(-1);
input.push(2);
input.push(4);
input.push(9);

stack<int> tmpStack = sort(input);

while (!tmpStack.empty()){
cout << tmpStack.top()<< " ";
tmpStack.pop();
}
}```
`20 9 6 4 2 -1`

### Java程序使用遞歸對堆棧進行排序

```import java.util.*;

class SortStack{

public static Stack<Integer> sort(Stack<Integer> input){

Stack<Integer> tmpStack = new Stack<Integer>();

while(!input.isEmpty()){
int tmp = input.pop();

while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){
input.push(tmpStack.pop());
}

tmpStack.push(tmp);
}
return tmpStack;
}

public static void main(String args[]){

Stack<Integer> input = new Stack<Integer>();

Stack<Integer> tmpStack=sort(input);

while (!tmpStack.empty()){
System.out.print(tmpStack.pop()+" ");
}
}
}```
`20 9 6 4 2 -1`

## 複雜度分析

### 時間複雜度

O（n ^ 2） 其中n是堆棧中元素的數量。 由於我們將元素從臨時堆棧推回原始堆棧，以防臨時堆棧的頂部小於要推入的元素。 為了更好地理解，請考慮降序序列並嘗試運行該算法。

### 空間複雜度

O（N） 因為我們為n個元素使用了臨時堆棧空間。 該算法不計算原始堆棧使用的空間。