資料結構：堆疊
堆疊（Stack）是資料結構中一種常見且基礎的結構，它具有後進先出（LIFO, Last In First Out）的特性。在許多程式設計場景中，堆疊扮演著重要角色，尤其在遞迴處理、表達式求值、函數呼叫管理等方面更是不可或缺。
一、堆疊的定義
堆疊是一種線性資料結構，只允許在一端進行資料的插入與刪除操作。這一端被稱為”堆疊頂端”（Top），插入操作稱為”壓入”（Push），刪除操作稱為”彈出”（Pop）。
堆疊遵循後進先出（LIFO）的原則，即最後壓入堆疊的元素最先被彈出。
二、堆疊的基本操作
1. 初始化堆疊
建立一個空堆疊，準備進行後續操作。
2. 壓入（Push）
將元素放入堆疊頂端。
3. 彈出（Pop）
從堆疊頂端移除元素。
4. 取頂端元素（Peek 或 Top）
取得堆疊頂端的元素，但不移除。
5. 判斷堆疊是否為空（IsEmpty）
檢查堆疊內是否沒有元素。
三、堆疊的程式碼範例
以下為 C++ 範例：
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
cout << "堆疊頂端元素: " << s.top() << endl; // 30
s.pop();
cout << "彈出一個後，堆疊頂端元素: " << s.top() << endl; // 20
cout << "堆疊是否為空: " << (s.empty() ? "是" : "否") << endl;
return 0;
}四、堆疊的特性
- 後進先出（LIFO）：最後加入的元素最先被取出。
- 插入和刪除操作僅在堆疊頂端進行。
- 操作時間複雜度為 O(1)。
五、堆疊的實作方式
1. 陣列實作
使用陣列作為底層儲存結構，但容量固定，可能會造成空間浪費或超出容量。
2. 鏈結串列實作
使用單向或雙向鏈結串列，每次壓入或彈出時調整指標，避免容量限制。
六、堆疊的應用
1. 遞迴函數的執行
系統會利用堆疊保存函數呼叫過程中的參數與返回位址。
2. 表達式求值
中序轉後序表達式、計算後序表達式值等，都可使用堆疊處理。
3. 括號匹配
檢查表達式中的括號是否成對匹配。
4. 瀏覽器的返回功能
瀏覽器的返回按鈕可視為堆疊的應用，最新的頁面最先返回。
七、堆疊的優缺點
優點：
- 操作簡單，高效能，Push 和 Pop 時間複雜度皆為 O(1)。
- 適合處理後進先出的需求場景。
缺點：
- 容量有限（陣列實作），需要擴充時較麻煩。
- 僅能存取頂端元素，無法隨機存取。
八、堆疊的時間與空間複雜度
| 操作 | 時間複雜度 |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Top | O(1) |
| IsEmpty | O(1) |
空間複雜度：O(n)，n 為堆疊中元素數量。
九、最佳實踐
- 若需頻繁存取非頂端元素，堆疊不適合，考慮陣列或鏈結串列。
- 使用 STL 提供的
stack類別，避免自行實作常見功能。 - 確保 Push 和 Pop 操作的邏輯正確，避免堆疊溢出或空堆疊操作。
十、結論
堆疊作為基本資料結構，在許多場景下都有著不可替代的地位。熟練掌握堆疊的特性與操作，不僅有助於理解遞迴和函數呼叫機制，更能幫助我們在處理特定類型問題時編寫出高效、簡潔的程式碼。