《数据结构与算法-王争》学习笔记,记录备查

基本概念

某个数据集合值涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,这种结构就叫做“栈”。

  • 栈是一种操作受限的线性表。
  • 后进者先出,先进者后出。

  • 用数组实现的栈叫 顺序栈

  • 用链表实现的栈叫 链式栈

操作

入栈

入栈,操作时直接将数据压入栈即可,操作有点想在数组和链表尾部添加节点。时间复杂度为O(1)。

出栈

出栈,操作时依次出站找到需要出站的节点,出站即可。

动态扩容

为了节省存储空间(不需要额外存储next指针),栈长基于数据来构建。数据一旦定义后,大小是固定的。当栈满后,如何入栈呢?只能扩容。即再申请一个更大的数组空间,把数据copy过去后,继续入栈。此时的时间复杂度为O(n)。

那我们得到入栈的最好时间复杂度为O(1),最差时间复杂度为O(n)。根据均摊分析法,入栈是有在极个别的情况下时间复杂度为O(n),它可以均谈到N次的copy中,所以得到平均时间复杂度为O(1)。

应用

在函数调用中的应用

函数调用栈,是栈数据结构的经典案例。函数执行时,操作系统给线程分配了一个栈类型的内存空间。当一个函数执行时,会将函数入栈,当函数返回后,再出栈。当函数有错误的时候,我们便能根据这个调用栈来很快的定位问题。

表达式求值中的应用

表达式求值,借助两个栈:

  • 操作数栈:存储操作数
  • 运算符栈:存储运算符

当表达式求值时,从左向右遍历表达式,当遇到数字,就压入操作数栈,当遇到运算符,就与运算符栈栈顶的运算符比较优先级,若比栈顶的运算符优先级高,则将当前运算符压入运算符栈。若比栈顶运算符底或相同,则从操作数栈顶去两个操作数,进行计算,将结果压入操作数栈,继续比较。

在括号匹配中使用

可以使用栈来判断括号是否合法,即是否左右匹配。

遍历一个带括号的表达式,遇到左括号就将其压入栈,遇到一个右括号,就将对应的左括号出栈,当遍历过程中,遇到不能匹配的右括号或栈中没有匹配的左括号时,即为不合法。当遍历完,栈为空,则表示合法。