栈和队列，因为其特殊的性质，如果巧妙利用，可以解决许多原本比较复杂的问题，而且还是 BFS 和 DFS 的基础，这一讲我们就来看看对于栈和队列的相关知识。
更新历史
- 2019.08.05：编入新系列
- 2016.01.22：完成初稿
栈与队列
栈和队列是比较典型的 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 的排队处理
实现方式
- 数组实现 - 需要一个变量来标记队列头及队列尾的位置
- 链表实现 - 需要保存表尾，处理表头的时候注意操作顺序
与栈的组合
- 利用一个栈和一个队列可以用来判断回文串
队列的进阶使用
- 优先队列
- 插入队列的元素有一定的顺序要求
- 每次插入实际上是某种意义上搜索和排序的过程
- 可以用数组来模拟实现
- 可以看作是『最大堆』或『最小堆』
解题策略
对于栈和队列的题目，一定要意识到这两个数据结构背后所代表的含义。
比方说，有一类问题有这样的特性：当前节点的解依赖后驱节点。也就是说，对于某个当前节点，如果不能获知后驱节点，就无法得到有意义的解。这类问题可以通过栈(或等同于栈的若干个临时变量)解决：先将当前节点入栈，然后看其后继节点的值，直到其依赖的所有节点都完备时，再从栈中弹出该节点求解。某些时候，甚至需要反复这个过程：将当前节点的计算结果再次入栈，直到其依赖的后继节点完备。
更进一步来看，只要是利用递归的过程，其实都可以去用栈来模拟，毕竟递归实际上就是一个隐式的栈调用。
具体解题的时候，从最基本的情况出发，根据题意推倒整个计算流程。这样做的好处是：
- 确保自己正确地理解了题目
- 从简单的情况出发，找找解题思路。该方法特别适用于递归，动态编程等题目类型
基本解题策略
- 如果需要追踪最大/最小值，可以考虑使用另一个栈
- 遍历子树的过程是一个自上而下结构：从顶层出发，逐渐向下扩散。所以考虑递归或者栈
- 有一类问题有这样的特性：当前节点的解依赖后驱节点。这类问题可以通过栈(或等同于栈的若干个临时变量)解决：先将当前节点入栈，然后看其后继节点的值，直到其依赖的所有节点都完备时，再从栈中弹出该节点求解。某些时候，甚至需要反复这个过程：将当前节点的计算结果再次入栈，直到其依赖的后继节点完备
- 由于栈的LIFO特性，可以利用栈数据结构消除递归。递归通常用函数调用自身实现，在调用的时候系统会分配额外的空间，并且需要用栈指针记录函数返回的位置，故额外开销(overhead)比较大