摘要：栈（stack）是算法竞赛和系统开发中的核心数据结构，本文将全面解析C++ STL中stack容器的使用技巧，助你掌握LIFO（后进先出）的精髓。

一、栈的本质与应用场景

栈是一种后进先出（LIFO）的线性数据结构，如同自助餐厅的餐盘堆：

• 浏览器前进/后退功能
• 函数调用栈
• 表达式求值
• 撤销操作（Undo）实现
• 括号匹配检查

二、STL stack基础操作

1. 头文件与声明

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

// 基本声明方式
stack<int> numStack;          // 存储整数的栈
stack<string> textStack;      // 存储字符串的栈
stack<pair<int, char>> complexStack; // 存储复杂类型的栈

2. 核心操作接口

操作	时间复杂度	功能描述
push(value)	O(1)	元素入栈
pop()	O(1)	移除栈顶元素
top()	O(1)	访问栈顶元素
empty()	O(1)	检查栈是否为空
size()	O(1)	返回栈中元素个数

3. 基本操作演示

stack<int> s;

// 元素入栈
s.push(10);  // 栈底: [10]
s.push(20);  // 栈底: [10, 20] ← 栈顶
s.push(30);  // 栈底: [10, 20, 30] ← 栈顶

cout << "栈顶元素: " << s.top() << endl;  // 输出30
cout << "栈大小: " << s.size() << endl;   // 输出3

// 元素出栈
s.pop();     // 移除30
cout << "新栈顶: " << s.top() << endl;    // 输出20

// 清空栈
while (!s.empty()) {
    s.pop();
}

三、关键注意事项

1. 空栈访问危险

stack<int> emptyStack;
// 错误示范：运行时崩溃！
// cout << emptyStack.top() << endl;
// emptyStack.pop();

// 正确做法：先检查非空
if (!emptyStack.empty()) {
    cout << emptyStack.top() << endl;
    emptyStack.pop();
}

2. 栈的底层容器

// 默认使用deque作为底层容器
stack<int> defaultStack;  

// 指定vector作为底层容器
stack<int, vector<int>> vecStack;  

// 指定list作为底层容器
stack<int, list<int>> listStack;  

3. 栈不支持遍历

// 错误：栈没有迭代器
// for(auto it = s.begin(); it != s.end(); ++it) 

// 正确访问方式：通过临时栈复制
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

四、经典应用：括号匹配检测

bool isValidParentheses(string expr) {
    stack<char> s;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else {
            if (s.empty()) return false;  // 右括号多余
            
            char top = s.top();
            s.pop();
            
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;  // 括号类型不匹配
            }
        }
    }
    return s.empty();  // 检查左括号是否全部匹配
}

// 测试用例
cout << isValidParentheses("({[]})") << endl;  // 1 (true)
cout << isValidParentheses("([)]") << endl;    // 0 (false)

五、性能优化技巧

1. 预先分配内存（当使用vector底层时）

vector<int> vec;
vec.reserve(1000);  // 预先分配内存
stack<int, vector<int>> myStack(vec);

2. 自定义栈元素类型

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

// 存储树节点的栈
stack<TreeNode*> nodeStack;  

3. 使用emplace避免拷贝（C++11）

stack<pair<int, string>> complexStack;

// 传统push需要构造临时对象
complexStack.push(pair<int, string>(1, "text"));

// 使用emplace直接构造
complexStack.emplace(2, "better");  // 效率更高

六、stack与其他容器对比

特性	stack	vector	deque	list
访问方式	仅栈顶	随机访问	随机访问	顺序访问
插入位置	仅顶部	任意位置	任意位置	任意位置
删除位置	仅顶部	任意位置	任意位置	任意位置
内存结构	依赖底层容器	连续内存	分段连续	非连续内存
典型用途	LIFO场景	动态数组	双端队列	频繁插入删除

七、综合应用：表达式求值

int evaluateExpression(string expr) {
    stack<int> values;
    stack<char> ops;

    for (int i = 0; i < expr.length(); i++) {
        if (expr[i] == ' ') continue;
        
        if (isdigit(expr[i])) {
            int num = 0;
            while (i < expr.length() && isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            values.push(num);
            i--;
        }
        else if (expr[i] == '(') {
            ops.push(expr[i]);
        }
        else if (expr[i] == ')') {
            while (ops.top() != '(') {
                applyOp(values, ops);
            }
            ops.pop(); // 移除 '('
        }
        else { // 运算符
            while (!ops.empty() && precedence(ops.top()) >= precedence(expr[i])) {
                applyOp(values, ops);
            }
            ops.push(expr[i]);
        }
    }
    
    while (!ops.empty()) {
        applyOp(values, ops);
    }
    
    return values.top();
}

八、最佳实践总结

1. 安全第一：操作前用empty()检查栈状态
2. 选择底层容器：根据场景选择deque（默认）、vector或list
3. 利用RAII：使用局部栈自动管理资源
4. 优先emplace：C++11以上使用emplace避免拷贝
5. 禁止遍历：栈设计上不支持遍历操作
6. 内存管理：大容量栈预先分配内存
7. 线程安全：多线程环境需自行加锁（STL stack非线程安全）