当前位置：首页 > news >正文

蓝桥杯STL stack

news 2025/8/15 14:04:21

STL stack 概述

栈（stack）是一种遵循**后进先出（LIFO）**原则的线性数据结构，仅允许在栈顶进行插入和删除操作。STL（Standard Template Library）中的 stack 是一个容器适配器，基于其他容器（如 deque 或 list）实现，默认使用 deque 作为底层容器。

栈的基本操作

初始化栈

STL stack 的初始化需要包含头文件 <stack>，并指定元素类型。

#include <stack>
using namespace std;stack<int> s; // 初始化一个存储整数的栈

入栈操作（push）

将元素添加到栈顶。

s.push(10); // 栈内元素: [10]
s.push(20); // 栈内元素: [10, 20]
s.push(30); // 栈内元素: [10, 20, 30]

出栈操作（pop）

移除栈顶元素，但不返回其值。

s.pop(); // 移除30，栈内元素: [10, 20]

访问栈顶元素（top）

返回栈顶元素的值，但不移除它。

int top_element = s.top(); // top_element = 20

检查栈是否为空（empty）

返回布尔值，判断栈是否为空。

bool is_empty = s.empty(); // 栈不为空，is_empty = false

获取栈的大小（size）

返回栈中元素的个数。

int stack_size = s.size(); // stack_size = 2

栈的典型应用场景

括号匹配问题
检查表达式中的括号是否匹配，例如 {[()]} 是合法的，而 {[(])} 是非法的。
表达式求值
实现中缀表达式转后缀表达式（逆波兰表达式），并计算其值。
深度优先搜索（DFS）
用栈模拟递归过程，避免递归调用带来的额外开销。

蓝桥杯真题示例：括号匹配问题

问题描述

给定一个只包含 (、)、[、]、{、} 的字符串，判断其括号是否匹配。

解决思路

遍历字符串，遇到左括号（(, [, {）时入栈。
遇到右括号时，检查栈顶是否是对应的左括号：
- 如果是，弹出栈顶。
- 如果不是，直接返回不匹配。
遍历结束后，栈为空则匹配，否则不匹配。

完整代码

#include <iostream>
#include <stack>
#include <string>
using namespace std;bool is_valid(string s) {stack<char> st;for (char c : s) {if (c == '(' || c == '[' || c == '{') {st.push(c);} else {if (st.empty()) return false;char top = st.top();if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) {st.pop();} else {return false;}}}return st.empty();
}int main() {string s = "{[()]}";cout << (is_valid(s) ? "Valid" : "Invalid") << endl;return 0;
}