【不周山之算法与数据结构】肆 栈和队列

栈和队列,因为其特殊的性质,如果巧妙利用,可以解决许多原本比较复杂的问题,而且还是 BFS 和 DFS 的基础,这一讲我们就来看看对于栈和队列的相关知识。


系列文章

基本上编程中重要的内容,都在这里了。

栈与队列

栈和队列是比较典型的 ADT,所谓 ADT,就是实际上内存中没有类似的数据结构对应,具体的操作是人为增加的设定,是为 Abstract,但是同时它们也被当做数据类型来用,是为 Data Type,于是就成为 ADT。

因为比较简单的缘故,这里大概说一下要点:

性质

  • 后入先出
  • Last-In / First-Out

支持的操作:

  • push - 入栈
  • peek - 查看栈顶
  • pop - 弹出栈顶元素

常见应用

  • 程序执行 - 函数调用和返回实际上就是入栈出栈的内容,详情见我的『深入理解计算机系统』系列
  • 解析 - Parsing
  • 计算 postfix 表达式的值 - 例如 4 + 3 可以写成 4 3 +

需要注意的问题

  • 在栈为空的时候执行 pop,会导致 underflow

实现方式

  • 数组实现 - 需要一个变量来标记栈顶位置
  • 链表实现 - 插入元素时对表头操作需要注意

常见题目

  • 括号匹配
  • 翻转字符串
  • 模拟递归(N 皇后问题)

队列

性质

  • 先入先出
  • First-In / First-Out

支持的操作:

  • Enqueue - 入队列
  • Dequeue - 出队列

常见应用

  • Round-robin 调度机制 - 处理器处理进程或服务器处理请求(负载均衡)
  • 输入/输出 处理
  • 网络中 packet 的排队处理

实现方式

  • 数组实现 - 需要一个变量来标记队列头及队列尾的位置
  • 链表实现 - 需要保存表尾,处理表头的时候注意操作顺序

与栈的组合

  • 利用一个栈和一个队列可以用来判断回文串

队列的进阶使用

  • 优先队列
    • 插入队列的元素有一定的顺序要求
    • 每次插入实际上是某种意义上搜索和排序的过程
    • 可以用数组来模拟实现
    • 可以看作是『最大堆』或『最小堆』

解题策略

对于栈和队列的题目,一定要意识到这两个数据结构背后所代表的含义。

比方说,有一类问题有这样的特性:当前节点的解依赖后驱节点。也就是说,对于某个当前节点,如果不能获知后驱节点,就无法得到有意义的解。这类问题可以通过栈(或等同于栈的若干个临时变量)解决:先将当前节点入栈,然后看其后继节点的值,直到其依赖的所有节点都完备时,再从栈中弹出该节点求解。某些时候,甚至需要反复这个过程:将当前节点的计算结果再次入栈,直到其依赖的后继节点完备。

更进一步来看,只要是利用递归的过程,其实都可以去用栈来模拟,毕竟递归实际上就是一个隐式的栈调用。

具体解题的时候,从最基本的情况出发,根据题意推倒整个计算流程。这样做的好处是:

  1. 确保自己正确地理解了题目
  2. 从简单的情况出发,找找解题思路。该方法特别适用于递归,动态编程等题目类型

基本解题策略

  • 如果需要追踪最大/最小值,可以考虑使用另一个栈
  • 遍历子树的过程是一个自上而下结构:从顶层出发,逐渐向下扩散。所以考虑递归或者栈
  • 有一类问题有这样的特性:当前节点的解依赖后驱节点。这类问题可以通过栈(或等同于栈的若干个临时变量)解决:先将当前节点入栈,然后看其后继节点的值,直到其依赖的所有节点都完备时,再从栈中弹出该节点求解。某些时候,甚至需要反复这个过程:将当前节点的计算结果再次入栈,直到其依赖的后继节点完备
  • 由于栈的LIFO特性,可以利用栈数据结构消除递归。递归通常用函数调用自身实现,在调用的时候系统会分配额外的空间,并且需要用栈指针记录函数返回的位置,故额外开销(overhead)比较大

附录

捧个钱场?