栈

栈

栈是只允许在一端进行插入、删除操作的线性表，遵循后进先出（LIFO）原则；栈可以通过数组或链表实现，通常用于存储和管理程序运行时的数据；比如，当函数被调用时，其局部变量和返回地址等信息会被压入栈中，而当函数调用结束时，这些信息会被弹出栈，函数得以返回；

此外，栈还有一些高级应用，如：

• 中缀表达式转换为后缀表达式：在计算器设计中，后缀表达式（逆波兰表达式）更易于求值；
• 符号匹配：在编译器设计中，用于检查输入的字符串是否与某种语言中的符号匹配；
• 计算后缀表达式的值：直接从后缀表达式求值；
• 实现函数调用和递归：在调用函数时，会用到栈来保存返回地址和局部变量；
• 文本编辑器的撤销操作：每次撤销操作，相当于在栈中添加一个操作记录，当执行撤销时，则从栈中移除这些记录；
• 浏览器后退按钮的实现：浏览器的历史记录可以看作是一个栈，每次浏览新的网页就压栈，点击后退按钮则出栈；

Ⓜ️

栈的数学性质：对 n 个不同元素进栈，出栈元素的不同排列个数为1/(N + 1) * C(n, 2n)；