定义

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的数据结构。这意味着最后添加进栈的元素会是第一个被移除的。栈的操作主要有两个：压栈（push），即在栈顶添加一个元素；弹栈（pop），即移除栈顶的元素。此外，通常还有一些辅助操作，如查看栈顶元素（peek或top），检查栈是否为空等。

应用

栈在计算机科学中有着广泛的应用，包括但不限于：

1. 函数调用栈：操作系统使用栈来管理函数调用。每当调用一个函数时，其返回地址和参数被压入调用者的栈中。当函数执行完成后，这些信息被用来返回到程序的上一个执行点。
2. 括号匹配：编译器使用栈来检查程序中的括号是否正确匹配。每当遇到一个开括号时，它就被压入栈中，遇到闭括号时，栈顶的开括号被弹出。如果在任何时刻栈为空时遇到闭括号，或者遍历完字符串后栈不为空，则括号未正确匹配。
3. 后缀表达式求值：栈可以用来评估后缀（逆波兰）表达式，这是一种没有括号，操作符位于操作数之后的数学表达式表示方法。
4. 历史记录：在许多应用程序中，如Web浏览器，栈用于维护访问历史。每次用户访问新页面，地址就被压入栈中。用户点击后退按钮时，最近访问的地址被弹出。

相关算法

1. [[找出全部合法的出栈序列]]
2. [[判断序列的出栈合法性]]
3. 深度优先搜索（DFS）：在图和树的遍历中，栈用于跟踪访问路径，尤其是在深度优先搜索中。
4. 迷宫求解：利用栈来存储路径，寻找从起点到终点的路线。
5. 逆波兰表达式求值：使用栈对后缀表达式进行求值，其中操作数被压入栈中，遇到操作符时，从栈中弹出所需数量的操作数，进行计算后结果再次压入栈中。
6. 回溯算法：在解决如八皇后问题等需要回溯的算法中，栈用于存储之前的状态。当需要回溯时，可以恢复到之前的状态。