双端队列

915考纲中并没有双端队列，同样没有共享栈，但后者却考了。

因此双端队列虽然目前没有考过，但今年也许就会考呢hhh

双端队列是限定插入和删除操作在表两端进行的线性表。

双端队列可以在任何一端进行插入和删除操作，而一般队列要求在一端插入元素，在另一端删除元素。

在双端队列进队时，左端进的元素排列在队列中右端进的元素的前面，右端进的元素排列在队列中左端进的元素的后面；在双端队列出队时，无论是左端还是右端出队，先出的元素排列在后出的元素的前面。

设有一个双端队列，输入序列1,2,3,4，那么从左端输入，在表中是[4,3,2,1]；从右端输入，在表中是[1,2,3,4]。

因此，若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

双端队列本质上还是一个线性表，只不过修改了输入输出规则。可以从左端输出由右端插入的元素，同理，可以从右端输出由左端插入的元素。

这种数据结构结合了队列和栈的特点，既遵循先进先出（FIFO）的原则，又实现了后进先出（LIFO）的原则。

输出受限的双端队列

允许在一端进行插入和删除，但在另一端只允许插入的双端队列。

允许在一端进行插入和删除，但在另一端只允许删除的双端队列。

设有一个双端队列，输入序列为1,2,3,4，试分别求出以下条件的输出序列。

(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。

(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。

(3) 既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。

令左端为end1，右端为end2。假设end1端输入1,2,3,4，则end2端的输出相当于队列的输出，即1,2,3,4；而end1端的输出相当于栈的输出， $n=4$ 时仅通过end1端有14种输出序列（由Catalan公式得出)，仅通过end1端不能得到的输出序列有 $4!-14=10$ 种；

1,4,2,3 \quad 2,4,1,3 \quad 3,4,1,2 \quad 3,1,4,2\quad 3,1,2,4 \\ 4,3,1,2\quad 4,1,3,2\quad 4,2,3,1\quad 4,2,1,3\quad 4,1,2,3

通过end1和end2端混合输出，可以输出这10种中的8种，参看下表。其中， $S_L,X_L$ 分别代表end1端的进队和出队， $X_R$ 代表end2端的出队。

输出序列	进队出队顺序	输出序列	进队出队顺序
1,4,2,3	$S_LX_RS_LS_LS_LX_LX_RX_R$	3,1,2,4	$S_LS_LS_LX_LS_LX_RX_RX_R$
2,4,1,3	$S_LS_LX_LS_LS_LX_LX_RX_R$	4,1,2,3	$S_LS_LS_LS_LX_LX_RX_RX_R$
3,4,1,2	$S_LS_LS_LX_LS_LX_LX_RX_R$	4,1,3,2	$S_LS_LS_LS_LX_LX_RX_LX_R$
3,1,4,2	$S_LS_LS_LX_LX_RS_LX_LX_R$	4,3,1,2	$S_LS_LS_LS_LX_LX_LX_RX_R$

剩下两种是不能通过输入受限的双端队列输出的，即4,2,3,1和4,2,1,3。

注解：

栈的输出序列的个数是卡特数（Catalan Numbers），公式为 $C_n=\frac{1}{n+1}C^n_{2n}$

由end1端不能得到的序列个数是 $n$ 的全排列减去能得到的。那十种是怎么来的？它全给写出来了，这无疑是一项非常耗费时间的操作，在实际考试中不太可能（选择题就排除法），因此这里仅学习它的思想。

(2)问同理，(3)是(1)和(2)问的交集。

初试为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5，则不能得到的出队序列是（）

5,4,3,1,2	5,3,1,2,4	4,2,1,3,5	4,1,3,2,5

解：模拟。以5,4,3,1,2为例，1（左右进均可），2（右进），3（左进），4（左进），5（左进）

**另解：**1(左右进均可)，2不管怎么进都得和1相邻，所以4,1,3,2,5不能得到。秒了。

若以1,2,3,4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是()

1,2,3,4	4,1,3,2	4,2,3,1	4,2,1,3

**解：**由例题2的另解方法可以得到4,1,3,2和4,2,3,1不能由输入受限的双端队列得到，然后再模拟输出受限的双端队列，先都入队4,3,2,1，然后左出得4，右出得4,1，后面同理。因此4,2,3,1为答案。

注意：双端队列虽然是两个队列共享一个存储空间，但是每个队列只有一个指针。