邓公数据结构与算法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 的 栈混洗? 通过 栈 能实现,线性复杂度的算法。

  • https://blog.csdn.net/became_a_wolf/article/details/49002593
  • https://www.cnblogs.com/Inkblots/p/4950331.html

延时

队列