邓公数据结构与算法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-栈和队列