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 --> [e-mail]

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

定义

只允许从两端插入、两端删除的线性表
如果只使用其中的一端的插入、删除操作，则双端队列的效果等同于栈
从而可以引申出另外两种特殊的双端队列

• 输出受限的双端队列：只允许从两端插入、一端删除
• 输入受限的双端队列：只允许从一端插入、两端删除

考点：判断输出序列的合法性

题目：如果数据元素输入序列是1，2，3，4，则哪些输出序列是合法的，哪些是非法的？
首先知道这些输入序列一共有$A_4^4=4!=24$种可能性
使用卡特兰数可以计算出一共有14种合法的出栈序列: $\frac{1}{n+1}{C}_n^{2n}=\frac{1}{4+1}{C}_4^8=14$
卡特兰数的公式还是需要记住的, 不需要证明, 但是要会使用
再看一下输入受限的双端队列和输入受限的双端队列

---

需要记住的是：栈中合法的序列, 双端队列中也一定合法

---

这种题目一般在选择题中出现
像这道题目, 输入顺序是1, 2, 3, 4, 那么在3之前, 1和2肯定已经输入进去了, 然后就可以看给你的选项中, 1和2是怎么排列的。

• 在输出受限的队列中, 因为只能从右边出, 如果给你的序列是1在2之前, 那么肯定是1要在右, 2要在左, 接下来要做的就是如何利用两端插入拼凑出你要的输出顺序
• 在输入受限的队列中，由于只能从一端输入，在一个元素出栈之前，其他的序号较小的元素就已经可以确定他们在队列里面的相对位置，接下来就只要验证，能不能根据左右两边的删除操作来拼凑出后续的这些输出序列