C / C++ / 系统课时
用 stack 处理后进先出任务
用 stack 处理后进先出任务
有些任务只允许操作“最后放进去”的数据,例如撤销最近一次编辑、解析嵌套括号或执行深度优先过程。std::stack 正是为这种后进先出规则设计的容器适配器,它主动限制访问方式,让代码直接表达这种约束。
学习目标
- 掌握
std::stack的push、top、pop、empty和size - 理解后进先出为什么适合撤销与括号匹配
- 判断什么时候应该使用
stack,什么时候应直接使用其他容器
stack 的访问限制就是它的价值
栈遵循 LIFO,也就是 Last In, First Out:最后压入的数据最先取出。std::stack 不提供随机访问,也不允许像普通序列容器那样直接遍历全部元素,常用操作只有栈顶附近的几个接口。
push(value):把元素压到栈顶。top():访问栈顶元素,但不删除它。pop():删除栈顶元素,没有返回值。empty():判断栈是否为空。size():取得当前元素数量。
调用 top() 或 pop() 前必须保证栈非空。需要“取出并删除”时,应先读取 top(),再调用 pop(),不能写成从 pop() 接收返回值。
撤销功能也是同样的结构:每执行一个可撤销操作,就把恢复所需的信息压栈;用户点击撤销时,只需要处理最近压入的记录。较早的记录自然留在下面等待后续撤销。
用括号匹配实践后进先出
嵌套括号要求最后打开的括号最先闭合。例如在 (a[b]{c}) 中,{ 必须先由 } 关闭,然后才轮到更早出现的 [ 和 (。这与栈的访问顺序完全一致。
下面的完整程序忽略普通字符,只检查 ()、[] 和 {} 是否正确配对。
#include <iostream>
#include <stack>
#include <string>
bool matches(char open, char close) {
return (open == '(' && close == ')') ||
(open == '[' && close == ']') ||
(open == '{' && close == '}');
}
bool isValid(const std::string& text) {
std::stack<char> opens;
for (char ch : text) {
// 左括号暂存,等待后面最近出现的右括号与它匹配。
if (ch == '(' || ch == '[' || ch == '{') {
opens.push(ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
// 右括号出现时,只能与当前栈顶的左括号配对。
if (opens.empty() || !matches(opens.top(), ch)) {
return false;
}
opens.pop();
}
}
return opens.empty();
}
int main() {
std::cout << std::boolalpha;
std::cout << "valid: " << isValid("(a[b]{c})") << '\n';
std::cout << "invalid: " << isValid("([)]") << '\n';
}预期输出:
valid: true
invalid: false处理右括号时必须先检查 empty()。如果栈已经为空,说明出现了没有对应左括号的右括号;如果栈顶类型不匹配,例如 ([)] 中遇到 ) 时栈顶仍是 [, 也应立即判定失败。遍历结束后还要再次检查栈是否为空,否则说明仍有左括号没有关闭。
为什么这里不用 vector 直接模拟
当然可以用 std::vector 的 push_back、back 和 pop_back 模拟同样的行为,但 std::stack 能把“不允许访问中间元素”直接写进接口约束。看到参数类型是 std::stack,读代码的人就知道算法只关心最近压入的数据。
标准 std::stack 是容器适配器,默认通常使用 std::deque 作为底层容器。大多数业务代码无需依赖这个实现细节,只需要按照栈接口编程即可。
什么时候不该使用 stack
如果算法需要遍历全部元素、访问任意下标、在中间插入数据或按照其他顺序取元素,std::stack 的限制就会成为阻碍,此时应直接选择 vector、deque、关联容器或其他更匹配的数据结构。
判断是否适合栈,可以问一个简单问题:下一次要处理的数据,是否永远是最近加入而尚未处理的那一个? 如果答案是肯定的,撤销记录、括号匹配、表达式求值以及许多深度优先过程都很适合用栈表达。