一疊盤子
想像食堂裡高高的一疊盤子。你把盤子加在最上面，也從最上面取盤子，絕不會從中間抽一個。最後放上去的盤子最先被取走——這就是後進先出，即 LIFO。
堆疊是一種抽象資料型別：它由你能對它*做什麼*來定義，而不是由它怎麼實作來定義。真正的操作只有三個。
- push(x)：把 x 放到堆疊頂。
- pop()：移除並回傳堆疊頂元素。
- top() / peek()：查看堆疊頂元素但不移除。
push 3 top -> | 3 |
| | 2 |
v | 1 |
'---' bottom
pop -> 3 top -> | 2 |
| 1 |
'---'使用 std::stack
C++ 標準函式庫直接給你一個現成的堆疊。三種操作都在 O(1) 內完成——常數時間，無論堆疊有多高。
#include <stack> #include <iostream> std::stack<int> s; s.push(1); s.push(2); s.push(3); std::cout << s.top(); // 3 (the last one pushed) s.pop(); // removes 3 std::cout << s.top(); // 2
自己手寫一個
堆疊簡單到你能用一個陣列（或像 `std::vector` 這樣的動態陣列）幾行就搭出來。"堆疊頂"不過是最後一個被填的位置——在末尾加或刪都是 O(1)，無需移動元素。
#include <vector>
struct Stack {
std::vector<int> data;
void push(int x) { data.push_back(x); } // O(1) amortized
int top() { return data.back(); } // O(1)
void pop() { data.pop_back(); } // O(1)
bool empty() { return data.empty(); }
};如果 vector 偶爾得擴容，為什麼 `push_back` 還是 O(1)？因為擴容時容量翻倍，那次偶發的昂貴複製被攤薄到許多次便宜的推入上——這就是所謂的攤銷 O(1)。你在基礎篇講動態陣列時見過這一點。
堆疊出現在哪裡
一旦你認出 LIFO 這個形狀，堆疊無處不在。呼叫堆疊正是程式記住每次函式呼叫後該返回哪裡的機制——每深入一層遞迴就推入一個堆疊框，每返回一次就彈出一個。編輯器裡的復原會最先彈出你最近的那次操作。而程式碼裡的括號配對，是堆疊的經典習題。
括號配對是這樣的：從左到右掃描。遇到左括號就推入；遇到右括號就彈出並檢查是否配對。一旦出現不匹配，或掃描結束時堆疊不為空，括號就不平衡。
// Is a string of () [] {} balanced?
bool balanced(const std::string& s) {
std::stack<char> st;
for (char c : s) {
if (c=='(' || c=='[' || c=='{') st.push(c);
else {
if (st.empty()) return false; // closer with nothing open
char o = st.top(); st.pop();
if ((c==')'&&o!='(') || (c==']'&&o!='[') ||
(c=='}'&&o!='{')) return false; // wrong match
}
}
return st.empty(); // leftover openers => unbalanced
}