江
江小南
V1
2023/02/14阅读:16主题:萌绿
【数据结构】双端队列
1. 回顾

栈:只允许从一端插入和删除的线性表(先进后出:FILO)。

队列:只允许从一端插入,另一端删除的线性表(先进先出:FIFO)。
2. 双端队列
1. 双端队列

双端队列:只允许从两端插入,两端删除的线性表。
若只使用其中一端插入、删除操作,则效果等同于栈。
2. 输入受限的双端队列

输入受限的双端队列:只允许从一端插入,两端删除的线性表。
3. 输出受限的双端队列

输出受限的双端队列:只允许从两端插入,一端删除的线性表。
3. 思考题
若数据元素输入序列为1,2,3,4,则哪些输出序列是合法的,哪些是非法的?

(A)3、2、4、1
(B)4、3、1、2
(C)1、4、2、3
(D)4、2、1、3
解析:题目中没有明确说是那种序列,就要从栈、队列、双端队列等多个角度思考。4个数字的所有排列组合顺序有 种情况。由卡特兰数:
得出对于栈的情况有14种合法出栈序列。
同时,在栈中合法的序列,在双端队列中也一定合法。
A选项看成一个栈,首先入栈1、2、3,然后3、2依次出栈,4入栈,再4出栈,最后1出栈。合法。
B看成输入受限的双端队列。首先4个元素输入,4、3依次出列,1从另一端出列,最后2出列,合法。
C看成输入受限的双端队列。首先1输入,然后1出队列。再2、3、4依次输入,4出列,2从另一端出列,最后3出列,合法。
D无法实现,不合法。
4. 小结

回顾:共享栈。
作者介绍
江
江小南
V1