数据结构与算法 - 线性表 - 栈
约 798 字大约 3 分钟
数据结构与算法栈
2023-09-08
《数据结构与算法-王争》学习笔记，记录备查
基本概念
某个数据集合值涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这种结构就叫做“栈”。
栈是一种操作受限的线性表。
后进者先出，先进者后出。
用数组实现的栈叫 顺序栈
用链表实现的栈叫 链式栈
操作
入栈
入栈，操作时直接将数据压入栈即可，操作有点想在数组和链表尾部添加节点。时间复杂度为O(1)。
出栈
出栈，操作时依次出站找到需要出站的节点，出站即可。只涉及栈顶节点排除查找操作，时间复杂度也为O(1)。
动态扩容
为了节省存储空间（不需要额外存储next指针），栈长基于数据来构建。数据一旦定义后，大小是固定的。当栈满后，如何入栈呢？只能扩容。即再申请一个更大的数组空间，把数据copy过去后，继续入栈。此时的时间复杂度为O(n)。
那我们得到入栈的最好时间复杂度为O(1)，最差时间复杂度为O(n)。根据均摊分析法，入栈是有在极个别的情况下时间复杂度为O(n)，它可以均谈到N次的copy中，所以得到平均时间复杂度为O(1)。
应用
在函数调用中的应用
函数调用栈，是栈数据结构的经典案例。函数执行时，操作系统给线程分配了一个栈类型的内存空间。当一个函数执行时，会将函数入栈，当函数返回后，再出栈。当函数有错误的时候，我们便能根据这个调用栈来很快的定位问题。
表达式求值中的应用
表达式求值，借助两个栈：
- 操作数栈：存储操作数
- 运算符栈：存储运算符
当表达式求值时，从左向右遍历表达式，当遇到数字，就压入操作数栈，当遇到运算符，就与运算符栈栈顶的运算符比较优先级，若比栈顶的运算符优先级高，则将当前运算符压入运算符栈。若比栈顶运算符底或相同，则从操作数栈顶去两个操作数，进行计算，将结果压入操作数栈，继续比较。最后剩余栈中量阿哥操作数和一个运算符，直接计算清空栈，结束。
在括号匹配中使用
可以使用栈来判断括号是否合法，即是否左右匹配。
遍历一个带括号的表达式，遇到左括号就将其压入栈，遇到一个右括号，就将对应的左括号出栈，当遍历过程中，遇到不能匹配的右括号或栈中没有匹配的左括号时，即为不合法。当遍历完，栈为空，则表示合法。