数据结构-3.7.双端队列
一.双端队列的三种形式：
双端队列也可以是只在一端删除和添加，此时就是栈；
双端队列在一端添加，另一端输出，此时就是队列；
二.判断输出序列合法性：
题目：若数据元素输入序列为1，2，3，4，则哪些输出序列是合法的，哪些是非法的？
共有24种排列方式：
1.双端队列只在一端删除和添加：此时双端队列也是栈
2，4，1，3不行，因为4出栈时说明3已经入栈了，下一个出栈的只能是3，而不是1。
下图红色标注的输出序列都不合法：
栈中合法的序列，双端队列中也一定合法。
2.双端队列只能一端插入，两端删除：
如果此时双端队列变为只能一端插入，两端删除时，栈中合法的序列在该双端队列中也一定合法，因此只需再验证栈中
不合法的序列就可以得知哪些序列在该双端队列合法：
比如4，3，2，1就不合法，因为4出去后，说明1，2，3已经进入，下一个出栈的要么是1(左边出)，要么是3(右边出)，
不可能是2出栈。
下图红色标注的输出序列都不合法：
3.双端队列只能一端删除，两端插入：
如果此时双端队列变为只能一端删除，两端插入时，栈中合法的序列在该双端队列中也一定合法，因此只需再验证栈中
不合法的序列就可以得知哪些序列在该双端队列合法：
比如出栈序列1，4，2，3，1先从左或者右进入再出去，4出栈时说明2，3已经进栈，逆推：如果出栈顺序是4，2，3，说明栈里的排列是3，2，4(注：出栈只能从一端出)，进栈可以2先从左或者右进入，再3从左进栈，就形成3，2，最后4从右进栈，就形成了3，2，4，说明该出栈序列合法。
比如出栈序列4，1，3，2，逆推：由于出栈只能从一端出，因此栈里排列只能是2，3，1，4，显然错误，因为如果形成了1，4，那么左边必须是3，2，不可能是2，3，因为3比2后进栈(另一种思路：4出栈后，如果前面是1，那么1的前面只可能是2，不可能是3，因为3比2后进栈)
下图红色标注的输出序列都不合法：
三.总结：
原文地址：https://blog.csdn.net/ADCvbV/article/details/142675740
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！