堆疊 (Stack) 簡介
歡迎！在本章中，我們將探討計算機科學中最基礎且使用最頻繁的數據結構之一：堆疊 (Stack)。堆疊在追蹤任務、反轉數據，甚至是協助電腦執行子程序（subroutine）方面都非常有用。讀完這些筆記後，你將會明白它們的運作原理、如何使用它們，以及為什麼它們對於你的 AQA A Level 考試如此重要。
如果數據結構起初看起來有點抽象，不用擔心——我們會用大量的日常例子來讓你清楚理解！
什麼是堆疊？
堆疊是一種抽象數據類型 (Abstract Data Type, ADT)。這意味著它是一個關於數據應如何組織和存取的概念模型。它遵循一條非常明確的規則，稱為 LIFO，即 後進先出 (Last-In, First-Out)。
類比：想像一個自助餐廳的托盤堆。
1. 你把一個新托盤放到這堆東西的最頂端。
2. 如果你想拿一個托盤，你只能拿最頂端的那一個。
3. 第一個放下的托盤（最底部的那個）必須等到它上面所有的托盤都被移走後，才能被取走。
關鍵術語：LIFO
在堆疊中，你添加的最後一個項目，就是你必須移除的第一個項目。你永遠只能與堆疊的「頂端」進行互動。
快速回顧：LIFO 規則
• Last In (後進)
• First Out (先出)
• 把它想像成一罐品客薯片——工廠最後放進去的薯片，就是你第一個吃到的！
基本的堆疊運算
根據你的課程大綱，你需要確切知道如何描述和應用這五種運算：
1. Push (推入)
Push 運算會將新項目添加到堆疊的頂端。
步驟如下：
1. 檢查堆疊是否已滿（以避免堆疊溢位 Stack Overflow）。
2. 增加頂端指標 (top pointer)（將其向上移動一個位置）。
3. 將新數據插入該位置。
2. Pop (彈出)
Pop 運算會從堆疊的頂端移除該項目，並通常會回傳其值。
步驟如下：
1. 檢查堆疊是否為空（以避免堆疊下溢 Stack Underflow）。
2. 存取目前頂端指標處的數據。
3. 減少頂端指標（將其向下移動一個位置）。
3. Peek (查看) 或 Top
Peek 運算會回傳頂端元素的值但不會將其移除。就像看一眼最上面的托盤是什麼顏色，而不用把它拿起來一樣。
4. Test for Empty Stack (isEmpty)
這會檢查堆疊中是否有任何項目。如果頂端指標處於起始位置（根據實作方式通常為 -1 或 0），則堆疊為空 (empty)。
5. Test for Stack Full (isFull)
如果堆疊是使用固定大小的陣列（靜態數據結構）來實作的，它可能會空間不足。此運算會檢查頂端指標是否已達到最大容量。
重點總結
Push 用於添加，Pop 用於移除，Peek 用於查看。在 Push 之前務必檢查堆疊是否已滿 (Full)，在 Pop 之前檢查是否為空 (Empty)！
實作：記憶體中的運作方式
在考試中，你可能會被問到堆疊實際上是如何構建的。最常見的情況是，堆疊是使用陣列 (array) 和頂端指標 (top pointer) 來實作的。
• 陣列 (Array)：儲存數據的連續記憶體位置。
• 頂端指標 (Top Pointer)：儲存目前頂端元素索引（位置）的變數。
你知道嗎？
當我們在 Pop 運算中「移除」一個項目時，數據並不會立即從記憶體中刪除。我們只是簡單地將頂端指標向下移動。電腦會將該「彈出」的空間視為空白，儘管舊的位元（bits）仍然存在，直到它們被新的 Push 運算覆蓋為止！
常見錯誤
• 指標位置：有些程式設計師將頂端指標設定在 \( -1 \)（表示堆疊為空），而有些則從 \( 0 \) 開始。請務必仔細閱讀考試題目，看看它是如何定義「空」的。
• 運算順序：Push 時，你必須在添加數據之前增加指標。而 Pop 時，你通常在減少指標之前獲取數據。
堆疊的實際應用
堆疊不僅僅存在於教科書中；它們幾乎被用於你使用的每一款軟體中！
1. 復原 (Undo) 按鈕
每次你在文書處理軟體中輸入一個字母，它都會被 Push 到一個堆疊中。當你按下「復原」時，電腦會從堆疊中 Pop 出最後的操作來將其撤銷。
2. 瀏覽器中的「返回」按鈕
當你瀏覽網站時，每個網址（URL）都會被 Push 到一個堆疊中。當你點擊「返回」時，目前的頁面會從堆疊中 Pop 出，顯示出前一個頁面。
3. 子程序呼叫 (堆疊幀 Stack Frames)
這是 AQA 課程大綱（4.1.1.15 節）的一個特定部分。當程式呼叫一個函數（子程序）時，它會使用堆疊幀 (stack frame) 來儲存：
• 返回位址 (Return addresses)：函數結束後要返回哪裡。
• 參數 (Parameters)：傳遞給函數的數據。
• 區域變數 (Local variables)：僅在該函數內部存在的變數。
4. 逆向波蘭表示法 (Reverse Polish Notation, RPN)
堆疊被用於評估 RPN 中的數學表達式（4.3.3.1 節）。例如，\( 3 + 4 \) 寫作 \( 3 \ 4 \ + \)。電腦將 3 和 4 Push 到堆疊中，然後當它看到 \( + \) 時，它會將兩者 Pop 出來，將它們相加，然後將結果再 Push 回堆疊。
快速回顧：堆疊的用途
• 回溯 (Backtracking)（復原/返回按鈕）
• 函數呼叫（遞迴和堆疊幀）
• 反轉數據
• 表達式評估 (RPN)
摘要表
運算 | 說明
Push | 將項目添加到頂端。增加指標。
Pop | 移除並回傳頂端項目。減少指標。
Peek | 回傳頂端項目但不移除它。
isEmpty | 如果堆疊中沒有項目，回傳 True。
isFull | 如果靜態堆疊達到最大容量，回傳 True。
考試重點總結
如果你看到關於堆疊的問題，請記住 LIFO。永遠要檢查溢位 (Overflow)（向已滿的堆疊 Push）和下溢 (Underflow)（從空的堆疊 Pop）。如果你能描述這些運算並畫出一個帶有移動指標的簡單陣列，那麼你離獲得高分就不遠了！