C++ stack
介绍
Stack（栈）是C++ STL（标准模板库）提供的一种容器适配器，它实现了一个后进先出（LIFO，Last In First Out）的数据结构。想象一堆盘子，你只能从顶部添加或移除盘子，这就是栈的工作原理。在C++中，stack作为适配器，它是基于其他容器（如deque、vector或list）实现的。
备注
默认情况下，C++ stack基于deque容器实现，但你可以使用不同的底层容器来创建stack。
基本特性
栈的主要特点：
- 后进先出(LIFO)：最后放入的元素将首先被取出
- 只能访问栈顶元素：无法直接访问栈内的其他元素
- 不支持迭代器：不能像其他容器一样使用迭代器遍历元素
- 不提供随机访问：不能通过索引访问栈中的元素
头文件和命名空间
要使用stack，需要包含以下头文件：
#include <stack>
并且stack位于std命名空间中：
using namespace std; // 或者使用 std::stack
创建和初始化栈
基本声明
// 创建一个空的整型栈
std::stack<int> myStack;
// 使用特定的底层容器（如vector）创建栈
std::stack<int, std::vector<int>> myVectorStack;
通过复制创建
std::stack<int> stack1;
// 添加一些元素到stack1
stack1.push(10);
stack1.push(20);
// 通过复制stack1创建stack2
std::stack<int> stack2(stack1);
栈的基本操作
添加元素 (push)
push 方法将元素添加到栈顶。
std::stack<int> myStack;
myStack.push(10); // 栈: [10]
myStack.push(20); // 栈: [10, 20]
myStack.push(30); // 栈: [10, 20, 30]
移除元素 (pop)
pop 方法移除栈顶元素。
myStack.pop(); // 栈: [10, 20]
警告
pop 方法不会返回被移除的元素。如果需要获取栈顶元素，应该在调用 pop 前先调用 top 方法。
访问栈顶元素 (top)
top 方法返回栈顶元素的引用，但不会移除它。
int topElement = myStack.top(); // topElement = 20
检查栈是否为空 (empty)
empty 方法返回栈是否为空。
bool isEmpty = myStack.empty(); // 如果栈为空则返回true，否则返回false
获取栈的大小 (size)
size 方法返回栈中元素的数量。
std::size_t stackSize = myStack.size(); // 返回栈中元素数量
交换内容 (swap)
swap 方法交换两个栈的内容。
std::stack<int> stack1, stack2;
stack1.push(10);
stack1.push(20);
stack2.push(100);
stack2.push(200);
stack1.swap(stack2); // 交换stack1和stack2的内容
完整示例
下面是一个完整的示例，展示了stack容器的基本用法：
#include <iostream>
#include <stack>
int main() {
// 创建一个空的整型栈
std::stack<int> myStack;
// 添加元素
myStack.push(10);
myStack.push(20);
myStack.push(30);
// 打印栈的大小
std::cout << "栈的大小: " << myStack.size() << std::endl;
// 访问栈顶元素
std::cout << "栈顶元素: " << myStack.top() << std::endl;
// 弹出栈顶元素
myStack.pop();
std::cout << "弹出后的栈顶元素: " << myStack.top() << std::endl;
// 检查栈是否为空
std::cout << "栈是否为空: " << (myStack.empty() ? "是" : "否") << std::endl;
// 依次弹出所有元素并打印
std::cout << "依次弹出所有元素: ";
while (!myStack.empty()) {
std::cout << myStack.top() << " ";
myStack.pop();
}
std::cout << std::endl;
// 再次检查栈是否为空
std::cout << "现在栈是否为空: " << (myStack.empty() ? "是" : "否") << std::endl;
return 0;
}
输出结果：
栈的大小: 3
栈顶元素: 30
弹出后的栈顶元素: 20
栈是否为空: 否
依次弹出所有元素: 20 10
现在栈是否为空: 是
栈的应用场景
栈在编程中有许多实际应用场景，包括但不限于：
1. 括号匹配
检查表达式中的括号是否匹配是栈的经典应用。
#include <iostream>
#include <stack>
#include <string>
bool areParenthesesBalanced(const std::string& expr) {
std::stack<char> s;
for (char c : expr) {
if (c == '(' || c == '[' || c == '{') {
s.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (s.empty()) return false;
char top = s.top();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
s.pop();
}
}
return s.empty();
}
int main() {
std::string expr = "{[()]}";
if (areParenthesesBalanced(expr))
std::cout << "括号匹配!" << std::endl;
else
std::cout << "括号不匹配!" << std::endl;
expr = "{[(])}";
if (areParenthesesBalanced(expr))
std::cout << "括号匹配!" << std::endl;
else
std::cout << "括号不匹配!" << std::endl;
return 0;
}
输出结果：
括号匹配!
括号不匹配!
2. 中缀表达式转后缀表达式（逆波兰表示法）
栈可用于将中缀表达式（如 a + b * c）转换为后缀表达式（如 a b c * +）。
3. 函数调用跟踪
操作系统和编译器使用栈来跟踪函数调用和返回地址。
4. 递归算法
递归过程中的函数调用隐式地使用了栈来存储中间状态。
5. 撤销机制
许多应用程序的撤销功能使用栈来记录操作历史。
自定义数据类型
栈也可以存储自定义数据类型：
#include <iostream>
#include <stack>
#include <string>
struct Person {
std::string name;
int age;
Person(std::string n, int a) : name(n), age(a) {}
};
int main() {
std::stack<Person> personStack;
personStack.push(Person("张三", 25));
personStack.push(Person("李四", 30));
std::cout << "栈顶的人: " << personStack.top().name
<< ", 年龄: " << personStack.top().age << std::endl;
personStack.pop();
std::cout << "弹出后栈顶的人: " << personStack.top().name
<< ", 年龄: " << personStack.top().age << std::endl;
return 0;
}
输出结果：
栈顶的人: 李四, 年龄: 30
弹出后栈顶的人: 张三, 年龄: 25
栈与递归的关系
栈和递归有着密切的关系。当程序执行递归调用时，系统使用调用栈来跟踪每个函数调用的环境。让我们看一个递归计算阶乘的例子，并分析栈的使用：
#include <iostream>
int factorial(int n) {
// 基本情况
if (n <= 1) {
return 1;
}
// 递归情况
return n * factorial(n - 1);
}
int main() {
int n = 5;
std::cout << n << "! = " << factorial(n) << std::endl;
return 0;
}
当执行 factorial(5) 时，调用栈的变化如下：
stack与其他容器的比较
了解stack与其他STL容器的区别有助于选择合适的数据结构：
-
stack vs vector:
- vector允许随机访问任何元素
- stack只允许访问最顶端元素
-
stack vs queue:
- stack是LIFO (后进先出)
- queue是FIFO (先进先出)
-
stack vs priority_queue:
- stack按照插入顺序访问元素
- priority_queue根据优先级访问元素
总结
C++ STL的stack容器提供了一个后进先出(LIFO)的数据结构实现，适用于需要后进先出特性的场景。它具有以下几个关键特点：
- 只能从顶部添加和删除元素
- 只能访问栈顶元素
- 不支持迭代和随机访问
- 提供简单的接口：push, pop, top, empty, size
通过本文的学习，你应该已经掌握了stack的基本用法和适用场景，能够在编程中合理地使用stack容器来解决问题。
练习题
- 基础练习: 使用stack反转一个字符串。
- 中级练习: 实现一个有效的四则计算器，使用栈来处理括号和运算符优先级。
- 高级练习: 实现一个使用两个栈的队列（一个栈用于入队操作，另一个栈用于出队操作）。
- 挑战练习: 使用栈来解决迷宫问题，跟踪访问路径。
参考资源
- C++ Reference: stack
- 《C++ Primer》和《Effective STL》等书籍的相关章节
- GeeksforGeeks - Stack in C++ STL