双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，如图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。