双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列，如图3-10所示。其元素的 逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。
图3-10 双端队列
在双端队列进队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排 列在队列中前端进的元素的后面。在双端队列出队时：无论前端还是后端出队，先出的元素 排列在后出的元素的前面。思考：如何由入队序列a, b, c, d得到出队序列d, c, a, b？
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列 称为输出受限的双端队列，如图3-11所示。
图3-11 输出受限的双端队列
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列 称为输入受限的双端队列，如图3-12所示。而如果限定双端队列从某个端点插入的元素只 能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。
图3-12 输入受限的双端队列
例如，设有一个双端队列，输入序列为1, 2, 3, 4，试分别求出以下条件的输出序列。
(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。
解答：
先看输入受限的双端队列，如图3-13所示。假设end1端输入1, 2, 3, 4，那么end2端的 输出相当于队列的输出：1, 2, 3, 4；而end1端的输出相当于栈的输出，n=4时仅通过end1端有14种输出序列（由前面提到的Catalan公式计算得出），仅通过end1端不能得到的输 出序列有4!-14=10种，它们是：
1,4,2,3 2,4, 1,3 3,4,1,2 3,1,4,2 3,1,2,4
4,3, 1,2 4,1,3,2 4,2,3,1 4,2,1,3 4, 1,2,3
通过end1和end2端混合输出，可以输出这10种中的8种，参看下表。其中，SL、XL 分别代表end1端的进队和出队，XR代表end2端的出队。
剩下两种是不能通过输入受限的双端队列输出的，即4, 2, 3, 1和4, 2, 1, 3。
再看输出受限的双端队列，如图3-14所示。假设end1端和end2端都能输入，仅end2 端可以输出。如果都从end2端输入，从end2端输出，就是一个栈了。当输入序列为1, 2, 3, 4时，输出序列有14种。对于其他10种不能得到的输出序列，通过交替从end1和end2端 输入，还可以输出其中8种。设SL代表end1端的输入，SR、XR分别代表end2端的输入 和输出，则可能的输出序列及进队和出队顺序见下表。
通过输出受限的双端队列不能得到的两种输出序列是4,1,3,2和4,2,3, 1。
综上所述：
1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是4,1,3,2。
2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是4,2,1,3。
3)既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的是4,2,3,1。
图3-10 双端队列
在双端队列进队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排 列在队列中前端进的元素的后面。在双端队列出队时：无论前端还是后端出队，先出的元素 排列在后出的元素的前面。思考：如何由入队序列a, b, c, d得到出队序列d, c, a, b？
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列 称为输出受限的双端队列，如图3-11所示。
图3-11 输出受限的双端队列
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列 称为输入受限的双端队列，如图3-12所示。而如果限定双端队列从某个端点插入的元素只 能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。
图3-12 输入受限的双端队列
例如，设有一个双端队列，输入序列为1, 2, 3, 4，试分别求出以下条件的输出序列。
(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
(3)既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列。
解答：
先看输入受限的双端队列，如图3-13所示。假设end1端输入1, 2, 3, 4，那么end2端的 输出相当于队列的输出：1, 2, 3, 4；而end1端的输出相当于栈的输出，n=4时仅通过end1端有14种输出序列（由前面提到的Catalan公式计算得出），仅通过end1端不能得到的输 出序列有4!-14=10种，它们是：
1,4,2,3 2,4, 1,3 3,4,1,2 3,1,4,2 3,1,2,4
4,3, 1,2 4,1,3,2 4,2,3,1 4,2,1,3 4, 1,2,3
通过end1和end2端混合输出，可以输出这10种中的8种，参看下表。其中，SL、XL 分别代表end1端的进队和出队，XR代表end2端的出队。
| 输出序列 | 进队出队顺序 | 输出序列 | 进队出队顺序 |
|---|---|---|---|
| 1,4,2, 3 | SLXRSLSLSLXLXRXR | 3,1,2,4 | SLSLSLXLXRSLXRXR |
| 2,4,1,3 | SLSLXLSLSLXLXRXR | 4,1,2,3 | SLSLSLSLXLXRXRXR |
| 3,4,1,2 | SLSLSLXLSLXLXRXR | 4,1,3,2 | SLSLSLSLXLXRXLXR |
| 3,1,4,2 | SLSLSLXLXRSLXLXR | 4,3，1,2 | SLSLSLSLXLXLXRXR |
再看输出受限的双端队列，如图3-14所示。假设end1端和end2端都能输入，仅end2 端可以输出。如果都从end2端输入，从end2端输出，就是一个栈了。当输入序列为1, 2, 3, 4时，输出序列有14种。对于其他10种不能得到的输出序列，通过交替从end1和end2端 输入，还可以输出其中8种。设SL代表end1端的输入，SR、XR分别代表end2端的输入 和输出，则可能的输出序列及进队和出队顺序见下表。
| 输出序列 | 进队出队顺序 | 输出序列 | 进队出队顺序 |
|---|---|---|---|
| 1,4,2,3 | SLXRSLSLSRXRXRXR | 3,1,2,4 | SLSLSRXRXRSRXLXR |
| 2,4,1,3 | SLSRXRSLSRXRXRXR | 4,1,2, 3 | SLSLSLSRXRXRXRXR |
| 3,4,1,2 | SLSLSRXRSRXRXRXR | 4,2,1,3 | SLSRSLSRXRXRXRXR |
| 3, 1,4,2 | SLSLSRXRXRSRXRXR | 4, 3, 1,2 | SLSLSRSRXRXRXRXR |
综上所述：
1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是4,1,3,2。
2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是4,2,1,3。
3)既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的是4,2,3,1。
