1. 題目

請編寫一個程序，對一個棧里的整型數據，按升序進行排序（即排序前棧里的數據是無序的，排序后最大元素位于棧頂）。要求最多只能使用一個額外的棧存放臨時數據，且不得將元素復制到別的數據結構中。

2. 解釋

• 輸入：一個無序的整數棧
• 輸出：一個升序排列的棧（棧頂為最大元素）
• 限制條件：
  1. 只能使用一個額外的棧作為輔助空間
  2. 不能使用其他數據結構（如數組、隊列等）
  3. 只能使用棧的標準操作（push, pop, peek, isEmpty）

3. 思路

核心算法：使用類似插入排序的思想，借助輔助棧實現排序

1. 初始化一個輔助棧 sortedStack（最終存放排序結果）
2. 當原棧不為空時：
   • 彈出原棧的棧頂元素 temp
   • 如果 sortedStack 不為空且 temp 比 sortedStack 的棧頂元素大，則將 sortedStack 的元素彈出并壓回原棧，直到找到 temp 的正確位置 ，否則將元素temp放入到 sortedStack
   • 將 temp 壓入 sortedStack
3. 最終 sortedStack 即為升序排列的棧

時間復雜度：O(n2)（最壞情況下需要反復移動元素）
空間復雜度：O(n)（僅使用一個額外棧）

4. 代碼

import java.util.Stack;public class StackSorter {public static Stack<Integer> sortStack(Stack<Integer> inputStack) {Stack<Integer> sortedStack = new Stack<>();while (!inputStack.isEmpty()) {int temp = inputStack.pop();// 將 sortedStack 中比 temp 大的元素移回 inputStackwhile (!sortedStack.isEmpty() && sortedStack.peek() > temp) {inputStack.push(sortedStack.pop());}sortedStack.push(temp);}return sortedStack;}public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(5);stack.push(1);stack.push(4);stack.push(2);stack.push(3);System.out.println("排序前: " + stack);Stack<Integer> sortedStack = sortStack(stack);System.out.println("排序后: " + sortedStack);}
}

輸出示例：

排序前: [5, 1, 4, 2, 3]
排序后: [1, 2, 3, 4, 5]  // 棧頂為5（最大元素）

5. 總結

• 關鍵點：利用輔助棧實現類似插入排序的算法，通過比較和臨時回退操作確保正確排序。
• 限制滿足：僅使用一個額外棧，沒有借助其他數據結構。
• 適用場景：適用于棧排序的經典問題，如面試題或算法練習。
• 優化思考：雖然時間復雜度為 O(n2)，但在棧操作限制下已是最優解法。

變體思考：

• 如果要降序排序（棧頂為最小元素），只需修改比較條件為 sortedStack.peek() < temp。
• 如果允許使用遞歸（隱式使用調用棧），可以嘗試遞歸解法，但空間復雜度可能更高。