(二)請以 2 個實際應用案例具體說明如何使用「stack」？（6 分）

堆疊（Stack）具備後進先出（LIFO, Last-In-First-Out）的核心特性，在系統底層、編譯器設計與應用程式開發中有極為廣泛的應用。

1. 程式執行與記憶體管理：函式呼叫堆疊（Call Stack）

作業系統與程式語言執行環境（Runtime）用堆疊追蹤函式的呼叫與返回狀態：

• 運作機制：呼叫函式時，將區域變數、傳入參數與返回位址（Return Address）打包成堆疊框架（Stack Frame / Activation Record）並推入（Push）；函式執行完畢後彈出（Pop），CPU 依返回位址回到呼叫點繼續執行。

• 典型現象：無窮遞迴或深層呼叫導致記憶體耗盡時，引發的 Stack Overflow（堆疊溢位）。

2. 編輯器與軟體系統：復原與重做（Undo / Redo）

文字編輯器（VS Code、Word）與繪圖軟體（Photoshop、Figma）普遍使用雙堆疊模型管理操作歷史：

• 復原堆疊（Undo Stack）：使用者執行新增、修改等操作時，狀態或逆向操作指令依序推入該堆疊。

• 重做堆疊（Redo Stack）：按下 Undo 時，從 Undo Stack 彈出最新狀態，並推入 Redo Stack；按下 Redo 則反向操作。若產生新編輯操作，Redo Stack 立即清空。

3. 網頁瀏覽器：歷史紀錄上一頁與下一頁（Back / Forward）

與 Undo/Redo 架構類似，瀏覽器維護兩個堆疊管理導航流程：

• 返回堆疊：記錄已拜訪的網址，點選「上一頁」時彈出目前頁面並移至前一頁。

• 前進堆疊：存放被退回的頁面，供「下一頁」快速前往。若在歷史狀態下點入新連結，前進堆疊會被清空。

4. 編譯器與語法解析（Parsing）

編譯器與直譯器在處理文字、符號與運算式時深度依賴堆疊：

• 括號匹配與語法平衡：檢查程式碼中的 ()、[]、{} 是否成對合法。遇左括號推入，遇右括號則彈出比對型態是否相符。

• 運算式轉換（Infix 轉 Postfix）：如 Dijkstra 提出的 調車場演算法（Shunting-yard Algorithm），利用堆疊暫存運算子，依運算子優先權調整輸出順序。

• 逆波蘭表示法求值（Postfix Evaluation）：遇運算元入疊，遇運算子彈出兩個運算元計算後再入疊，是計算機與虛擬機（如 JVM、PostScript、Forth）的核心運算基礎。

5. 圖形與樹狀演算法：深度優先搜尋（DFS）與回溯法（Backtracking）

• 深度優先搜尋（DFS）：除了遞迴實作，使用顯式堆疊（Explicit Stack）可避免深層遞迴造成的呼叫堆疊溢位。

• 回溯法應用：走迷宮演算法、八皇后問題、數獨求解等，將探索路徑的節點推入堆疊，若遇到死路則彈出退回上一節點繼續搜尋。

6. 標記語言解析（HTML / XML DOM 建構）

瀏覽器解析 HTML 或後端解析 XML 檔案時，遇起始標籤（如 <div>）推入堆疊，遇結束標籤（如 </div>）檢查是否與頂端標籤匹配並彈出，進而一步步建構出樹狀結構（DOM Tree）。