栈
一、什么是栈
栈是一种先进后出（Last In First Out，LIFO）的线性数据结构。就像一摞盘子，后放上去的盘子先被拿走，先放上去的盘子后被拿走。
核心操作：
* 入栈（push）：在栈顶添加元素
* 出栈（pop）：移除栈顶元素
* 取栈顶（top）：查看栈顶元素但不移除
* 判空（empty）：判断栈是否为空
* 获取大小（size）：获取栈中元素个数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、栈的两种实现方式
1. 数组实现栈（静态栈）
原理：用数组存储元素，用一个变量top指向栈顶位置。top初始为0表示空栈，入栈时先top++再赋值，出栈时top--。
优点：简单高效，访问速度快
缺点：大小固定，不能动态扩展
2. STL栈（标准模板库）
C++的STL提供了现成的栈容器，方便使用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、栈的经典应用
1. 括号匹配
原理：遍历字符串，遇到左括号入栈，遇到右括号则检查栈顶是否是对应的左括号。
2. 表达式求值（中缀转后缀）
原理：利用栈的优先级比较，将中缀表达式转换为后缀表达式再求值。
3. 单调栈（求下一个更大元素）
原理：维护一个单调递减的栈，当前元素比栈顶大时，栈顶的下一个更大元素就是当前元素。
4. 模拟递归（DFS）
栈可以用来模拟递归调用，避免递归深度过大的问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、栈的常见题型
1. 最小栈
设计一个栈，支持push、pop、top和getMin操作，getMin能在O(1)时间返回最小值。
2. 栈排序
使用辅助栈对栈进行排序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、栈的总结
特性 数组实现 STL实现 时间复杂度 O(1) O(1) 空间限制 固定大小 动态扩展 操作直观 需要手动管理 封装完善 适用场景 已知最大大小 大小不确定
栈的核心思想：
1. 先进后出是根本特性
2. 递归本质上就是栈的应用
3. 适用于需要回溯的场景
4. 常用于深度优先搜索（DFS）
5. 表达式求值、括号匹配等是经典应用
注意事项：
1. 使用数组实现时注意栈溢出（top超过MAXN）
2. 出栈前检查栈是否为空
3. 递归深度过大时考虑用栈模拟
4. 栈擅长处理具有嵌套结构的数据
