【数据结构】双端队列

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. 小结

回顾：共享栈。

【数据结构】栈的基本原理与实现