Stacks

歡迎來到堆疊（Stack）的世界！

你好！今天，我們要探索程式設計師工具箱中最基礎且實用的工具之一：堆疊（Stack）。這種資料結構屬於你 Oxford AQA 課程大綱中「基礎資料結構」的部分。

你可以把堆疊想像成現實生活中餐廳裡的餐盤堆，或是疊在一起的書本。如果你在最上面放了一本新書，這本書就是你必須先取走，才能拿到下面其他書的第一本書。這聽起來很簡單，但這個概念能幫助電腦管理從「復原（Undo）」按鈕到複雜數學計算等所有事務！

什麼是堆疊？

堆疊是一種線性資料結構，它遵循一條非常明確的規則，稱為 LIFO。
LIFO 代表 後進先出（Last-In, First-Out）。

想像一個糖果分配器（Pez dispenser）。你最後放進頂部的糖果，就是你使用時最先彈出來的那一顆。這正是電腦科學中堆疊的運作方式：最後加入的項目，就是最先被移除的項目。

需要記住的關鍵術語：

• LIFO：後進先出。這是堆疊的核心規則。
• 靜態資料結構：如果我們使用陣列（Array）來實作堆疊，它會有一個固定大小，在程式執行期間無法改變。
• 動態資料結構：如果堆疊的大小可以隨需求增加或減少，它就被視為動態的。

快速複習：為什麼它被稱為 LIFO？因為最後（Last）進去的項目，就是最先（First）離開的！

標準堆疊操作

為了使用堆疊，我們主要會用到三種「動作」或操作。如果這些名字聽起來很高級，別擔心；它們只是電腦的簡單指令而已。

1. 推入 (Push)

Push 操作會在堆疊的頂端加入一個新項目。
比喻：將一個新盤子放到一疊餐盤的最上方。

2. 彈出 (Pop)

Pop 操作會移除目前位於堆疊頂端的項目。
比喻：從那一疊盤子中取走最上方的那一個來使用。

3. 查看 (Peek / Top)

Peek 操作讓你查看位於堆疊頂端項目的值，但不會將其移除。
比喻：看一眼堆疊中最上方那本書的封面，而不把它拿起來。

常見錯誤：學生經常誤以為 pop 只是查看項目。請記住：pop 會將項目移除；而 peek 只是看一眼！

關鍵總結：使用 push 來新增，pop 來移除，以及 peek 來查看頂端內容。

如何使用陣列實作堆疊

在考試中，你需要了解如何使用一維陣列來建立堆疊。

為了追蹤我們目前的位置，我們使用一個特殊的變數，稱為頂端指標（Top Pointer）。這個指標會儲存目前堆疊頂端項目的索引（即位置編號）。

步驟拆解：新增項目 (Pushing)

1. 檢查堆疊是否已滿（以避免發生「堆疊溢位 Stack Overflow」）。
2. 將頂端指標加 1：\( top = top + 1 \)。
3. 將新項目插入到陣列中新的 \( top \) 位置。

步驟拆解：移除項目 (Popping)

1. 檢查堆疊是否為空（以避免發生「堆疊下溢 Stack Underflow」）。
2. 讀取或傳回目前 \( top \) 位置的項目。
3. 將頂端指標減 1：\( top = top - 1 \)。

檢查「已滿」或「為空」

• 空堆疊：通常，頂端指標會被設定為 \( -1 \)（或 \( 0 \)，取決於起始索引），以表示目前尚無項目。
• 滿堆疊：如果頂端指標等於陣列的最大容量，則堆疊已滿。此時嘗試 push 更多資料會導致堆疊溢位 (Stack Overflow) 錯誤！

關鍵總結：基於陣列的堆疊使用頂端指標來進行操作。在 push 前務必檢查是否已滿，在 pop 前務必檢查是否為空！

堆疊有什麼用途？

電腦非常愛用堆疊！以下是堆疊成為絕佳工具的幾個真實世界場景：

• 「復原 (Undo)」按鈕：你的文書處理軟體會保留一份你所做過的每一次變更的堆疊。當你按下復原時，它會將最後一次變更從頂端「彈出 (pop)」，讓你回到過去的操作狀態。
• 網頁瀏覽器記錄：當你按下「上一頁」按鈕時，瀏覽器會將你最後瀏覽的網址從堆疊中彈出。
• 副程式呼叫 (Stack Frames)：這對你的課程大綱來說是一個非常重要的概念！當程式呼叫副程式（函數）時，它會使用堆疊框架 (Stack Frame) 來儲存：
    1. 回傳位址 (Return address)（函數結束時要返回哪裡）。
    2. 參數 (Parameters)（傳入函數的資料）。
    3. 區域變數 (Local variables)（僅在函數內部使用的資料）。

你知道嗎？如果遞迴函數無窮無盡地執行導致電腦「崩潰」，通常是因為這些堆疊框架佔滿了記憶體——這正是知名網站「Stack Overflow」名稱的由來！

總結檢查清單

在結束之前，請確保你能回答以下問題：
• 我能解釋 LIFO 是什麼意思嗎？（後進先出）
• 我知道 push、pop 和 peek 之間的差別嗎？
• 我能描述頂端指標在 push 或 pop 期間如何變化嗎？
• 我了解什麼是堆疊溢位 (Stack Overflow) 和堆疊下溢 (Stack Underflow) 嗎？
• 我能列舉兩到三個堆疊的真實應用嗎？

如果覺得內容很多也不用擔心！只要記住「餐盤堆」的比喻，其他的概念就會慢慢融會貫通。你一定沒問題的！