栈 Stack 整理笔记
2026-10-07 20:59:57
发布于：广东
5阅读
0回复
0点赞
1. 概念
栈是一种运算受限的线性表，只允许在栈顶进行插入和删除操作。
栈顶：允许操作的一端
栈底：不允许操作的一端
特点：后进先出 / 先进后出，简称 LIFO / FILO
可以想象成一摞盘子：最后放上去的盘子，最先被拿走。
2. STL 定义
#include <stack>
using namespace std;
stack<int> s; // 定义一个整型栈
stack<char> st; // 定义一个字符栈
3. 常用函数
| 函数 | 作用 | 返回值 |
|---|---|---|
s.push(x) |
把 x 压入栈顶 | 无返回值 |
s.pop() |
删除栈顶元素 | 无返回值 |
s.top() |
获取栈顶元素 | 返回栈顶元素 |
s.empty() |
判断栈是否为空 | 空返回 true |
s.size() |
返回栈中元素个数 | 返回元素数量 |
⚠️ 最易错点：pop() 不返回值！
想取出并删除栈顶元素，必须：
int x = s.top(); // 先取值
s.pop(); // 再删除
不能写：
int x = s.pop(); // ❌ 错误，pop() 没有返回值
4. 遍历栈的标准写法
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
5. 数组模拟栈
竞赛中有时用数组模拟栈，速度更快：
const int N = 100010;
int stk[N];
int tt = 0; // 栈顶指针
stk[++tt] = x; // 入栈
tt--; // 出栈
int top_val = stk[tt]; // 取栈顶
bool empty = (tt == 0); // 判空
6. 常考：出栈序列判断
方法：直接模拟入栈出栈过程
例如入栈顺序为 1 2 3 4 5 6，判断出栈序列 1 3 5 2 4 6 是否合法：
出 1：入 1，出 1 → 栈空
出 3：入 2、3，出 3 → 栈中剩 2
出 5：入 4、5，出 5 → 栈中剩 2、4
出 2：此时栈顶是 4，2 被压在下面，无法先出
所以这个序列不合法。
🧠 记忆口诀
栈顶进，栈顶出；后进先出别记错。
pop 不返回值，取值必须用 top。
判断出栈序列，直接模拟最稳妥。
------------------------------------------------------------------------------------------------------------
相关代码讲解与注释
#include <bits/stdc++.h>
using namespace std;
int main() {
/* ==============================
1. 栈的基本定义与常用操作
============================== */
stack<int> st;
st.push(10); // 入栈，栈：10
st.push(20); // 入栈，栈：10 20，20 是栈顶
st.push(30); // 入栈，栈：10 20 30，30 是栈顶
cout << "栈顶元素：" << st.top() << endl; // 输出 30
cout << "栈大小：" << st.size() << endl; // 输出 3
st.pop(); // 弹出栈顶 30，栈变为：10 20
cout << "弹出后栈顶：" << st.top() << endl; // 输出 20
cout << "是否为空：" << st.empty() << endl; // 输出 0，表示非空
/* ==============================
2. 栈的遍历输出
注意：栈没有迭代器，只能用 top() + pop() 依次取出
============================== */
while (!st.empty()) {
cout << st.top() << " "; // 先取栈顶
st.pop(); // 再弹出栈顶
}
cout << endl;
// 输出结果：20 10
// 因为栈是后进先出，所以输出顺序与入栈顺序相反
/* ==============================
3. 输入逆序输出
这是栈最典型的入门应用
============================== */
int n;
cin >> n;
stack<int> st2;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
st2.push(x); // 依次入栈
}
// 依次出栈，就得到输入顺序的逆序
while (!st2.empty()) {
cout << st2.top() << " ";
st2.pop();
}
cout << endl;
/* ==============================
4. 括号匹配
遇到左括号入栈，遇到右括号检查栈顶是否匹配
============================== */
string s;
cin >> s; // 读取字符串
stack<char> st; // 定义字符栈
// 1. 遍历字符串中的每一个字符
for(int i = 0; i < s.size(); i++){
// 如果碰到左括号 '('，入栈（等待被匹配）
if(s[i] == '(') {
st.push('(');
}
// 如果碰到右括号 ')'，尝试匹配
else if (s[i] == ')'){
if(st.empty()){
// 栈空说明没有左括号来匹配当前的右括号，直接判定失败
cout << "NO";
return 0; // 提前结束程序，不再往下看
} else {
// 栈不空，弹出栈顶的左括号，表示成功匹配一对
st.pop();
}
}
// 2. 特殊终止条件：遇到 '@' 立即停止遍历
if(s[i] == '@') break;
}
// 3. 遍历结束后，检查栈中是否还有残留的左括号
if(st.empty()) {
// 栈空，说明所有的左括号都被匹配完了，合法
cout << "YES";
} else {
// 栈不空，说明有左括号落单了，非法
cout << "NO";
}
return 0;
}
/* ==============================
5. 数组模拟栈
竞赛中有时用数组模拟栈，速度更快
============================== */
const int N = 100010;
int stk[N];
int tt = 0; // 栈顶指针，tt == 0 表示栈空
stk[++tt] = 10; // 入栈
stk[++tt] = 20;
stk[++tt] = 30;
cout << "数组栈栈顶：" << stk[tt] << endl; // 输出 30
tt--; // 出栈
cout << "出栈后栈顶：" << stk[tt] << endl; // 输出 20
if (tt == 0) cout << "栈为空" << endl;
else cout << "栈非空" << endl;
return 0;
}
有帮助，赞一个