栈（stack）是 C++ STL 中经典的后进先出（LIFO, Last In First Out） 数据结构，所有操作仅在一端（栈顶）进行。它封装了底层容器（默认 deque），提供稳定、高效的入栈、出栈等接口，是解决括号匹配、表达式求值、函数调用栈等问题的核心工具。

---

一、核心概念与原理

1. 基本特性

• 操作位置：仅在栈顶（top） 进行插入和删除。
• 核心规则：后进先出（LIFO）。最后插入的元素，最先被移除。
• 底层容器：默认使用 deque（双端队列），也可指定 vector 或 list。
• 不支持迭代器：栈是容器适配器，不支持随机访问，只能通过接口操作。

2. 关键操作

成员函数	功能
push(值)	入栈：将元素添加到栈顶
pop()	出栈：移除栈顶元素（不返回值）
top()	获取栈顶元素的引用
size()	返回栈中元素个数
empty()	判断栈是否为空，为空返回 true
swap()	交换两个栈的内容（C++11 后常用）

---

二、定义与初始化

使用栈必须包含头文件 <stack>。定义时指定元素类型，默认容器为 deque。

1. 基础语法

#include <stack> // 必须包含头文件

// 格式: stack<元素类型, 容器类型> 栈名;
stack<int> st1;          // 最常用：int类型，默认deque容器
stack<char, vector<char>> st2; // 指定vector作为底层容器
stack<int, list<int>> st3;   // 指定list作为底层容器

2. 快速初始化示例

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

int main() {
    // 1. 创建空栈
    stack<int> st;
    
    // 2. 入栈操作
    st.push(10);
    st.push(20);
    st.push(30);
    
    return 0;
}

三、常用操作实战代码

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

int main() {
    // 创建一个int类型的栈
    stack<int> st;

    // 1. 判断栈是否为空
    if (st.empty()) {
        cout << "s1是空的" << endl;
    }

    // 2. 入栈操作 (0,1,2,3,4)
    for (int i = 0; i < 5; i++) {
        st.push(i);
    }
    cout << "入栈0~4后,栈内的数据个数:" << st.size() << endl;

    // 3. 出栈操作 (输出栈顶并移除)
    cout << "出栈:" << endl;
    while (!st.empty()) {
        // 输出栈顶元素
        cout << st.top() << endl;
        // 移除栈顶元素
        st.pop();
    }

    return 0;
}

运行结果

s1是空的
入栈0~4后,栈内的数据个数:5
出栈:
4
3
2
1
0

四、底层容器与注意事项

1. 为什么默认是 deque？

• 高效的头尾操作：deque 在头部和尾部插入 / 删除效率极高。
• 扩容成本低：相比 vector 一次性扩容复制所有数据，deque 扩容更轻量。

2. 可用容器限制

可以作为栈底层容器的类型必须支持以下成员函数：

• back()
• push_back()
• pop_back()
• empty()、size()

结论：

• ✅ 可用：deque（默认）、vector、list
• ❌ 不可用：forward_list（不支持 back ()）、array（不支持动态扩容）

五、常见应用场景

1. 括号匹配校验

#include <stack>
#include <string>
bool isValidParentheses(string s) {
    stack<char> st;
    for(char c : s) {
        if(c == '(') st.push(')');
        else if(c == '{') st.push('}');
        else if(c == '[') st.push(']');
        else if(st.empty() || st.top() != c) return false;
        else st.pop();
    }
    return st.empty();
}

2. 逆序输出

栈天然支持反转序列：

stack<int> st;
st.push(1); st.push(2); st.push(3);
while(!st.empty()) { cout << st.top(); st.pop(); } // 输出 321

六、核心总结

1. 核心口诀：栈顶操作，后进先出；push 入，pop 出，top 取顶。
2. 使用规范：
   • 包含头文件：#include <stack>
   • 访问成员：用 . 运算符（如 st.push()）
   • 动态管理：pop() 只删除不返回，需先 top() 取值再 pop()。
3. 性能：底层容器高效，入栈 / 出操时间复杂度均为 O(1)。