邓公数据结构与算法4-栈和队列
栈和队列 都是线性结构的特例，因此其实现都可以用 向量或列表 来实现。
STL 中 stack 的接口使用
栈的使用
栈与递归
递归算法所需的空间量，主要决定于最大递归深度。在达到这一深度的时刻，同时活跃的递归实例最多。
那么操作系统是如何实现函数（递归）调用的呢？如何同时记录调用与被调用函数（递归）实例之间的关系？如何实现函数（递归）调用的返回？又是如何维护同时活跃的所有函数（递归）实例的？
这些问题，都归结于栈。[课本 88 页]
场景一：逆序输出
逆序输出：conversion, 输出次序与处理过程颠倒，递归深度和输出长度不易预知。
进制转换
场景二：递归嵌套
具有自相似性的问题多可嵌套的递归描述，但因分支位置和嵌套深度并不固定，其递归算法的复杂度不易控制。栈结构及其操作天然的具有递归嵌套性，故可以高效的解决这类问题。
括号匹配
课本[92页]
算法其实很简单，主要是思考的过程。使用减治 和 分治 都不能解决这个问题。
从大规模问题到小规模问题并不完全等效。也就是分成子问题之后，不满足条件的情况下，合成大问题却可以满足情况。
用 栈 真的太合适了。而且可以推广到多种括号的情况。
栈混洗
借助一个中间 栈， 将 栈A 的数转移到 栈B 中去。称作 栈混洗(stack permutation).
在 pytorch 中根据 index 进行重新排列 permutation，实际上也是用的 栈 对吧？
index_select
n 个数的栈混洗的总数， 恰好是著名的 catalan 数
$$\dfrac{2n!}{(n+1)!n!}$$
怎么甄别出哪些不是栈混洗的序列呢？
这里有一个禁止的情况出现。对于任何三个互异的数
$1\le i < i < j < k \le n$ 出现 $k…,i,…,j$ 则必非为栈混洗。
怎么判断一个序列 B 是否是另一个序列 A 的 栈混洗？ 通过 栈 能实现，线性复杂度的算法。
延时
队列
邓公数据结构与算法4-栈和队列