本文最后更新于 34 天前，其中的信息可能已经有所发展或是发生改变。
一、什么是栈？
基本概念
栈（stack） 是一种 先进后出（First In Last Out, FILO） 的数据结构，它只有一个出口。
生活比喻
想象一叠盘子：
- 放盘子（入栈）：只能放在最上面
- 取盘子（出栈）：只能从最上面取
- 特点：最后放上去的盘子最先被取走
二、栈的重要特性
关键限制：不能遍历！
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
// ❌ 错误！栈不能遍历
// for (int i = 0; i < s.size(); i++) {
// cout << s[i] << " "; // 没有[]操作符！
// }
// ❌ 错误！栈没有迭代器
// for (auto it = s.begin(); it != s.end(); it++) {
// cout << *it << " ";
// }为什么不能遍历？
- 栈设计为只能访问顶部元素
- 如果允许遍历，就破坏了栈的FILO特性
- 如果需要遍历，应该使用vector或deque
三、stack的基本操作
1. 包含头文件和创建栈
#include <iostream>
#include <stack> // 必须包含stack头文件
using namespace std;
int main() {
// 创建栈
stack<int> s; // 创建一个空的int类型栈
return 0;
}2. 入栈操作（push）
stack<int> s;
// 向栈顶添加元素
s.push(10); // 栈：10（底部）
s.push(20); // 栈：10, 20
s.push(30); // 栈：10, 20, 30（顶部）
cout << "栈大小: " << s.size() << endl; // 输出：33. 查看栈顶元素（top）
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
cout << "栈顶元素: " << s.top() << endl; // 输出：30
// top()只查看，不删除元素
cout << "栈顶元素仍然是: " << s.top() << endl; // 输出：304. 出栈操作（pop）
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
cout << "出栈前栈顶: " << s.top() << endl; // 30
s.pop(); // 移除栈顶元素
cout << "出栈后栈顶: " << s.top() << endl; // 20
s.pop(); // 再移除一个
cout << "最后栈顶: " << s.top() << endl; // 105. 判断栈是否为空（empty）
stack<int> s;
if (s.empty()) {
cout << "栈是空的" << endl;
} else {
cout << "栈不是空的" << endl;
}
s.push(100);
if (!s.empty()) { // 取反操作
cout << "栈不是空的" << endl;
}6. 获取栈大小（size）
stack<int> s;
cout << "初始大小: " << s.size() << endl; // 0
s.push(10);
s.push(20);
s.push(30);
cout << "当前大小: " << s.size() << endl; // 3
s.pop();
cout << "出栈后大小: " << s.size() << endl; // 2四、完整示例演示
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<string> bookStack; // 创建一个书栈
cout << "=== 图书馆还书入栈 ===" << endl;
// 还书（入栈）
bookStack.push("《C++ Primer》");
bookStack.push("《算法导论》");
bookStack.push("《设计模式》");
cout << "当前栈顶书籍: " << bookStack.top() << endl; // 《设计模式》
cout << "书堆中有 " << bookStack.size() << " 本书" << endl;
cout << "\n=== 借书出栈 ===" << endl;
// 借书（出栈）
while (!bookStack.empty()) {
string currentBook = bookStack.top();
cout << "借出: " << currentBook << endl;
bookStack.pop();
if (!bookStack.empty()) {
cout << "下一本可借: " << bookStack.top() << endl;
} else {
cout << "书已借完！" << endl;
}
cout << "---" << endl;
}
cout << "最终书堆是否为空: " << (bookStack.empty() ? "是" : "否") << endl;
return 0;
}输出结果：
=== 图书馆还书入栈 ===
当前栈顶书籍: 《设计模式》
书堆中有 3 本书
=== 借书出栈 ===
借出: 《设计模式》
下一本可借: 《算法导论》
---
借出: 《算法导论》
下一本可借: 《C++ Primer》
---
借出: 《C++ Primer》
书已借完！
---
最终书堆是否为空: 是五、栈的常见应用场景
场景1：函数调用栈
void functionA() {
cout << "进入A函数" << endl;
// 函数调用时，信息入栈
}
void functionB() {
cout << "进入B函数" << endl;
functionA(); // 调用A函数
cout << "返回B函数" << endl;
// 函数返回时，信息出栈
}
int main() {
functionB(); // 调用B函数
return 0;
}场景2：括号匹配检查
#include <iostream>
#include <stack>
using namespace std;
bool checkParentheses(const string& expression) {
stack<char> s;
for (char c : expression) {
if (c == '(' || c == '[' || c == '{') {
s.push(c); // 左括号入栈
} else if (c == ')' || c == ']' || c == '}') {
if (s.empty()) return false; // 栈空但遇到右括号
char top = s.top();
s.pop();
// 检查括号是否匹配
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return s.empty(); // 栈应该为空
}
int main() {
string expr1 = "((a+b)*[c-d])";
string expr2 = "((a+b)*[c-d))"; // 不匹配
cout << expr1 << " : " << (checkParentheses(expr1) ? "匹配" : "不匹配") << endl;
cout << expr2 << " : " << (checkParentheses(expr2) ? "匹配" : "不匹配") << endl;
return 0;
}场景3：撤销操作（Undo）
#include <iostream>
#include <stack>
using namespace std;
class TextEditor {
private:
stack<string> undoStack; // 撤销栈
string currentText;
public:
void type(const string& text) {
undoStack.push(currentText); // 保存当前状态
currentText += text;
cout << "输入后: " << currentText << endl;
}
void undo() {
if (!undoStack.empty()) {
currentText = undoStack.top();
undoStack.pop();
cout << "撤销后: " << currentText << endl;
} else {
cout << "无法撤销" << endl;
}
}
};
int main() {
TextEditor editor;
editor.type("Hello");
editor.type(" World");
editor.type("!");
editor.undo(); // 撤销!
editor.undo(); // 撤销 World
return 0;
}六、重要注意事项
1. 空栈操作错误
stack<int> s;
// ❌ 危险操作：空栈调用top()或pop()
// cout << s.top() << endl; // 未定义行为，可能崩溃
// s.pop(); // 未定义行为
// ✅ 安全做法：先检查是否为空
if (!s.empty()) {
cout << s.top() << endl;
s.pop();
} else {
cout << "栈为空，不能操作" << endl;
}2. 栈的拷贝和赋值
stack<int> s1;
s1.push(1);
s1.push(2);
s1.push(3);
// 拷贝构造
stack<int> s2(s1); // s2现在和s1一样
// 赋值操作
stack<int> s3;
s3 = s1; // s3现在和s1一样
cout << "s1栈顶: " << s1.top() << endl; // 3
cout << "s2栈顶: " << s2.top() << endl; // 3
cout << "s3栈顶: " << s3.top() << endl; // 3七、stack的底层实现
stack实际上是容器适配器，默认基于deque实现：
// stack的底层实现大致如下：
template<typename T, typename Container = deque<T>>
class stack {
private:
Container c; // 底层容器
public:
void push(const T& value) { c.push_back(value); }
void pop() { c.pop_back(); }
T& top() { return c.back(); }
// ... 其他操作
};也可以基于其他容器：
#include <vector>
#include <list>
stack<int> s1; // 默认基于deque
stack<int, vector<int>> s2; // 基于vector
stack<int, list<int>> s3; // 基于list八、总结表格
| 操作 | 函数 | 说明 | 时间复杂度 |
|---|---|---|---|
| 入栈 | push(value) | 添加到栈顶 | O(1) |
| 出栈 | pop() | 移除栈顶元素 | O(1) |
| 查看栈顶 | top() | 返回栈顶元素 | O(1) |
| 判断空 | empty() | 栈是否为空 | O(1) |
| 获取大小 | size() | 元素个数 | O(1) |
九、练习题
练习1：数字反转
// 使用栈将数字的各位反转
// 输入：12345 → 输出：54321练习2：表达式求值
// 使用栈计算简单表达式
// 输入："3 4 + 5 *" → 输出：35练习3：浏览器前进后退
// 模拟浏览器历史记录
class Browser {
// 实现back()和forward()功能
};十、重点记住
- FILO原则：先进后出，像叠盘子
- 只能访问栈顶：不能遍历，不能随机访问
- 操作前检查空栈：避免未定义行为
- 常用操作：push、pop、top、empty、size
- 应用广泛：函数调用、括号匹配、撤销操作等
口诀：
栈是FILO结构，只能操作最上头
push放入顶，pop弹出顶
top看顶不删，empty判空否
遍历不允许，安全要记牢栈是编程中非常重要的数据结构，理解它的特性对学习算法和系统设计都很有帮助！