Stacks

基本數據結構：堆疊 (Stacks) (3.2.4)

歡迎來到奇妙的數據結構世界！我們已經學習過陣列（Arrays）和列表（Lists），現在要深入探討「堆疊」（Stacks）——這是計算機科學中最簡單，卻也是最核心的數據結構之一。

理解堆疊不只是為了死背定義，而是要掌握許多關鍵電腦運作背後的邏輯——從管理子程序（subroutines）到處理「復原」（Undo）功能，全都要靠這個簡單的概念。如果一開始覺得有點抽象，別擔心，我們會用生活中的例子來為你拆解！

1. 後進先出 (LIFO) 原則

堆疊最重要的特徵，在於它嚴格的排序原則：後進先出 (Last-In, First-Out, LIFO)。

想像一下咖啡廳裡的洗碗槽疊盤機：

• 當放入一隻新盤子時，它會放在最上面。（後進，Last In）。
• 當廚師需要盤子時，他們會從最上面拿走一隻。（先出，First Out）。

如果你依序放入盤子 A、B，然後是 C：

[A 在最底層，C 在最頂層。]
當你要取走盤子時，必須先拿走 C，然後才是 B，最後才能拿到 A。

記憶小撇步：LIFO

Last In, First Out（後進，先出）。你可以聯想到 Stack of Plates（堆疊盤子，簡稱 S & P）！

2. 堆疊的核心操作

課程大綱要求你必須了解並運用堆疊的三個主要操作，以及執行這些操作時所需的必要檢查。

Push (新增項目)

將新項目加入到堆疊頂部的操作稱為 Push（推入）。

步驟如下：
1. 檢查堆疊是否 已滿 (Full)（如果沒有空間，就無法 Push！）。
2. 若未滿，將新項目放置到目前的頂部位置。
3. 更新追蹤堆疊 頂部 (Top) 的指標或索引。

範例：將「蘋果」Push 到水果堆疊中，表示「蘋果」現在成為了新的頂部項目。

Pop (移除項目)

將堆疊頂部的項目移除並取出的操作稱為 Pop（彈出）。

步驟如下：
1. 檢查堆疊是否 為空 (Empty)（如果裡面什麼都沒有，就無法 Pop！）。
2. 若非空，將頂部位置的項目取回。
3. 更新指標或索引，將 頂部 (Top) 向下移動（即移除該項目）。

關鍵點：Pop 操作會移除該項目，並縮小堆疊的大小。

Peek (或 Top) (查看頂部項目)

Peek（有時稱為 Top）操作用於返回頂部元素的值，但不會將其從堆疊中移除。

比喻：稍微抬起最上面的盤子看一下下面的標籤，然後把它放回去。

3. 使用一維陣列實作堆疊

雖然現代程式語言通常有內建的堆疊函式庫，但你必須理解堆疊在底層是如何運作的，通常是透過 一維陣列 (One-dimensional array) 來達成。

堆疊指標 (Stack Pointer, Top of Stack)

使用陣列時（陣列大小固定），我們需要一個變數，通常稱為 堆疊指標 (Stack Pointer) 或 Top Of Stack，用來追蹤 LIFO 操作（Push/Pop）應該發生的位置。

此指標存儲的是最近加入元素所在的索引（位置）。

檢查堆疊是否為空或已滿

由於陣列容量固定，檢查邊界條件對於防止錯誤（例如嘗試 Push 到已滿的堆疊，這稱為 堆疊溢位 Stack Overflow）至關重要。

• 是否為空 (Is Empty?)：如果堆疊指標處於初始位置，則堆疊為空。如果我們定義陣列索引從 0 開始，指標通常在堆疊為空時初始化為 -1。若指標等於此初始值，則堆疊為空。
• 是否已滿 (Is Full?)：如果堆疊指標達到了底層陣列的 最大允許索引，則堆疊已滿。若陣列大小為 N，則最大索引為 \(N-1\)。

讓我們追蹤一個最大容量為 5（索引 0 至 4）的堆疊：
初始狀態：堆疊指標 (SP) = -1。

1. Push 項目 A： SP 加 1 變為 0。A 存於索引 0。
2. Push 項目 B： SP 加 1 變為 1。B 存於索引 1。
3. Push 項目 C： SP 加 1 變為 2。C 存於索引 2。
4. (堆疊陣列: [A, B, C, _, _]。SP = 2)
5. Pop： 取出索引 2 的項目 (C)。SP 減 1 變為 1。
6. (堆疊陣列: [A, B, _, _, _]。SP = 1)
7. Peek： 取出索引 1 的項目 (B)。SP 保持為 1。

實作重點總結

透過陣列實作堆疊需要管理 堆疊指標 (Stack Pointer)。PUSH 涉及增加指標並儲存數據；POP 涉及取出數據並減少指標。必須進行關鍵檢查，以確保指標不會低於最小索引（為空）或超過最大索引（已滿）。

4. 堆疊在計算機科學中的應用

堆疊不僅僅是理論，它是許多關鍵計算過程的基礎組成部分。你必須能夠描述堆疊作為合適數據結構的應用場景。

A. 子程序呼叫堆疊 (最重要用途！)

當程式執行時，系統會使用一個堆疊（即 呼叫堆疊 Call Stack）來管理函式或子程序的呼叫。

• 當子程序 A 呼叫子程序 B 時，系統必須記住 B 執行完後要返回 A 的哪個位置。這些資訊（即 返回地址 return address），連同任何 參數 (parameters) 和 區域變數 (local variables)（統稱為 堆疊框架 Stack Frame），都會被 Push 到呼叫堆疊中。(這直接連結到課程大綱 3.1.2.7 部分！)
• 當子程序 B 完成後，其堆疊框架會被 Pop 出來，程式便利用儲存的返回地址跳回 A 中的正確位置。

這種 LIFO 的過程確保了巢狀子程序會以呼叫的相反順序完成。

B. 「復原」(Undo) 功能

在文書處理軟體（如 Microsoft Word）或繪圖軟體（如 Photoshop）中，「復原」功能正是依賴堆疊來實現。

• 你執行的每一個動作（打字、繪圖、刪除）都會被 Push 到復原堆疊中。
• 當你按下「復原」時，最後加入的動作會從堆疊中 Pop 出來並執行逆向操作。

C. 表達式評估 (Expression Evaluation)

編譯器和直譯器使用堆疊來轉換和評估數學表達式，特別是在處理後序表示法（逆波蘭表示法）或前序表示法時。運算元（數字）通常會被 Push 到堆疊中；當遇到運算子時，必要的運算元會被 Pop 出來進行計算，計算結果再被 Push 回去。

你知道嗎？

我們常看到的錯誤訊息 "Stack Overflow"（也是一個著名的程式開發網站名稱），指的就是電腦內部呼叫堆疊因為記憶體耗盡而發生的錯誤。這通常是因為呼叫了太多函式卻沒有正確返回（常見於設計不當的遞迴程式，且缺少基底條件導致無窮迴圈）！

請持續練習這些概念，試著親手模擬堆疊運作，或是運用程式語言的函式庫實作看看！