【数据结构】线性数据结构——栈
1. 定义
栈（Stack）是一种线性数据结构，它遵循**后进先出（LIFO，Last In First Out）**的原则。也就是说，最后被插入的元素最先被取出。栈只允许在一端（栈顶，Top）进行数据的插入和删除操作。
2. 特点
-
后进先出： 最后加入栈的元素最先被移除。
-
受限操作： 栈只允许在栈顶进行插入（Push）和删除（Pop）操作。
-
只能访问栈顶元素： 通过 Peek/Top 操作获取栈顶元素，而不移除它。
-
空栈和栈满的状态： 空栈时无法弹出元素。在固定大小的栈中，栈满时无法继续插入。
3. 栈的基本操作
以C++ 的 STL（标准模板库）提供的 std::stack 类模板为例，以下是栈的常见基本操作：
- push(value)： 将元素压入栈顶。
- pop()： 弹出栈顶元素（不返回值，只移除）。
- top()： 获取栈顶元素，但不移除。
- empty()： 检查栈是否为空，返回 true 或 false。
- size()： 返回栈中元素的数量。
4. 栈的实现方式
栈可以通过数组或链表实现：
(1) 数组实现栈： 使用一个数组和指针表示栈顶位置。
优点：实现简单。
缺点：需要提前定义数组大小，容量固定，可能浪费空间。
(2) 链表实现栈： 使用链表节点动态存储元素。
优点：可以动态扩展，无需提前定义容量。
缺点：需要额外存储指针，空间效率略低于数组。
5. 栈的应用
栈因其后进先出的特性，在许多场景中非常有用：
-
括号匹配： 用于判断括号是否成对出现（如 {[()]}）。
-
表达式求值： 中缀表达式转后缀表达式，以及后缀表达式的计算。
-
函数调用管理： 栈用于保存函数调用的上下文（调用栈）。
-
深度优先搜索（DFS）： 栈用于保存节点的路径。
-
撤销与恢复操作： 在文本编辑器中，用栈保存用户操作的历史记录，实现撤销功能。