本文主要是介绍03-3.2.4 双端队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 👋 Hi, I’m @Beast Cheng
- 👀 I’m interested in photography, hiking, landscape…
- 🌱 I’m currently learning python, javascript, kotlin…
- 📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏,今后还会不断更新。🧑💻
此外,《程序员必备技能》专栏和《程序员必备工具》专栏(该专栏暂未开设)日后会逐步更新,感兴趣的小伙伴可以点一下订阅、收藏、关注!🚀
谢谢大家!🙏
定义
只允许从两端插入、两端删除的线性表
如果只使用其中的一端的插入、删除操作,则双端队列的效果等同于栈
从而可以引申出另外两种特殊的双端队列
- 输出受限的双端队列:只允许从两端插入、一端删除
- 输入受限的双端队列:只允许从一端插入、两端删除
考点:判断输出序列的合法性
题目:如果数据元素输入序列是1,2,3,4,则哪些输出序列是合法的,哪些是非法的?
首先知道这些输入序列一共有 A 4 4 = 4 ! = 24 A_{4}^{4}=4!=24 A44=4!=24种可能性
使用卡特兰数可以计算出一共有14种合法的出栈序列: 1 n + 1 C n 2 n = 1 4 + 1 C 4 8 = 14 \frac{1}{n+1}C_{n}^{2n}=\frac{1}{4+1}C_{4}^{8}=14 n+11Cn2n=4+11C48=14
卡特兰数的公式还是需要记住的, 不需要证明, 但是要会使用
再看一下输入受限的双端队列和输入受限的双端队列
需要记住的是:栈中合法的序列, 双端队列中也一定合法
这种题目一般在选择题中出现
像这道题目, 输入顺序是1, 2, 3, 4, 那么在3之前, 1和2肯定已经输入进去了, 然后就可以看给你的选项中, 1和2是怎么排列的。
- 在输出受限的队列中, 因为只能从右边出, 如果给你的序列是1在2之前, 那么肯定是1要在右, 2要在左, 接下来要做的就是如何利用两端插入拼凑出你要的输出顺序
- 在输入受限的队列中,由于只能从一端输入,在一个元素出栈之前,其他的序号较小的元素就已经可以确定他们在队列里面的相对位置,接下来就只要验证,能不能根据左右两边的删除操作来拼凑出后续的这些输出序列
这篇关于03-3.2.4 双端队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!