【C++ STL】 容器详解：stack 学习

在 C++ STL（标准模板库）中，stack 是 栈（LIFO 结构），它是一种 后进先出（Last In, First Out, LIFO） 的数据结构。栈的插入（push）和删除（pop）操作都在 栈顶 进行，适用于 递归调用、括号匹配、表达式求值 等场景。

1. stack 的基本特点

• 后进先出（LIFO）：最新入栈的元素最先被弹出。

• 仅允许访问栈顶元素：不能随机访问栈内的其他元素。

• 底层实现：通常基于 deque（双端队列），也可使用 vector 或 list 实现。

• 时间复杂度：所有操作（push、pop、top）的时间复杂度均为 O(1)。

2. stack 的基本用法

2.1 stack 的定义与初始化

stack<T, Container> s;
//T：存储的元素类型。
//Container：底层容器类型，默认为deque<T>

//定义一个存储整数的栈：
stack<int> myStack;

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    
    // 入栈
    s.push(10);
    s.push(20);
    s.push(30);
    
    // 访问栈顶元素
    cout << "栈顶元素: " << s.top() << endl;
    
    return 0;
}

输出：

栈顶元素: 30

可以看到，后进先出（LIFO） 规则。

2.2 插入与删除

s.push(40);  // 插入 40
s.pop();     // 弹出栈顶元素（40）

2.3 访问栈顶元素

cout << "栈顶元素: " << s.top() << endl;

2.4 检查栈是否为空

if (s.empty()) {
    cout << "栈为空" << endl;
}

2.5 获取栈大小

cout << "栈大小: " << s.size() << endl;

2.6 stack的内部实现

stack是一个容器适配器，它基于其他容器（如deque或list）实现。默认情况下，stack使用deque作为底层容器，但我们可以通过模板参数指定其他容器，例如vector或list。

底层容器的选择

• deque（默认）：deque支持高效的随机访问和两端操作，适合作为stack的底层容器。

• vector：vector在尾部插入和删除操作上效率很高，但需要注意内存重新分配的问题。

• list：list在任何位置的插入和删除操作效率都很高，但内存开销较大。

例如，使用vector作为底层容器：

stack<int, vector<int>> myStack;

3. stack 的应用场景

• 括号匹配：用于检测括号是否匹配，如 {[(...)]}

• 表达式求值：用于中缀表达式转后缀表达式（逆波兰表达式）。

• 函数调用栈：用于管理函数的递归调用。

• 撤销/回退操作：如文本编辑器的“撤销”功能。

3.1 括号匹配示例

#include <iostream>
#include <stack>
using namespace std;

bool isValid(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;
    cin >> s;
    cout << (isValid(s) ? "合法" : "不合法") << endl;
    return 0;
}

输入示例：

{[()]}

输出：

合法

4. stack 与 queue、priority_queue 的区别

总结

stack 是 C++ STL 中的 后进先出（LIFO） 容器，适用于 递归调用、括号匹配、表达式求值 等场景。其操作简单高效，适合管理 数据回溯 和 状态恢复 的需求。