链队就是采用链式存储结构存储队列，这里采用单链表来实现。链队的特点就是不存在队列满上溢的情况（其实这里也不太严格，内存满了就上溢了）。

1.链队的要素

链队也有两个特殊状态和两个操作。

（1）两个状态

1）队空状态。

lqu-＞rear==NULL或者lqu-＞front==NULL（为什么有两个，后边解释）

2）队满状态。

不存在队列满的情况（假设内存无限大的情况下不存在）。

（2）两个操作

1）元素进队操作（假设p指向进队元素）。

lqu-＞rear-＞next=p；lqu-＞rear=p；

2）元素出队操作（假设x存储出队元素）。

p=lqu-＞front；lqu-＞front=p-＞next；x=p-＞data；free（p）；

图3-6显示了一个链队的动态变化过程。由图3-6可以看出，front和rear任何一个为空都可以用来判定链队为空。

图3-6 链队元素的进队与出队

2.初始化链队算法

3.判断队空的算法

4.入队算法

5.出队代码

说明：

1）以上代码不需要记忆，读程序并且理解每一步操作的意义即可。

2）与链队相比，顺序队的定义、操作等都要简单，因此在考研的程序设计题目中，要尽量采用顺序队来解决问题，尽可能地避免用链队，除非题目明确规定要用链队。

◎模糊范围知识点积累

1.共享栈

相比于普通的顺序栈，共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计的，共享栈有很多新的特性。下面通过一个例题来了解共享栈。

【例3-4】 为了增加内存空间的利用率和减少溢出的可能性，当两个栈共享一片连续的内存空间时，应将两栈的（①）分别设在这片内存空间的两端，这样当（②）时，才产生上溢。

①：A.长度 B.深度 C.栈顶 D.栈底(www.daowen.com)

②：A.两个栈的栈顶同时到达栈空间的中心点

B.其中一个栈的栈顶到达栈空间的中心点

C.两个栈的栈顶在栈空间的某一位置相遇

D.两个栈均不空，并且一个栈的栈顶到达另一个栈的栈底

答案：D，C

由题干所述，两个栈共享一片连续的存储空间，可知这两个栈都是顺序栈（联想到顺序栈占用连续存储空间），进一步知，为顺序栈分配好的连续空间大小在栈的操作过程中不变，并且这个连续的存储空间有恒定不变的两端。于是自然想到，这两个栈的栈底分别位于存储空间的两端（因为我们已经学过顺序栈的栈底是不变的），因此①处应该选D；确定了栈底，则两栈栈顶必在存储空间内，显然当两栈顶相遇时，存储空间被用尽，会产生上溢，故②处选C。

2.双端队列

双端队列是一种插入和删除操作在两端均可进行的线性表。可以把双端队列看成栈底连在一起的两个栈。它们与两个栈共享存储空间的共享栈的不同之处是，两个栈的栈顶指针是向两端延伸的。由于双端队列允许在两端插入和删除元素，因此需设立两个指针：end1和end2，分别指向双端队列中两端的元素。

允许在一端进行插入和删除（进队和出队），另一端只允许删除的双端队列称为输入受限的双端队列，如图3-7所示；允许在一端进行插入和删除，另一端只允许插入的双端队列称为输出受限的双端队列，如图3-8所示。

图3-7 输入受限的双端队列

图3-8 输出受限的双端队列

关于双端队列的一些性质通过一个例题来介绍。

【例3-5】 设有一个双端队列，元素进入该队列的顺序是1，2，3，4。试分别求出满足下列条件的输出序列。

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

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

（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。

答：

先看输入受限的双端队列，如图3-7所示。假设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，1，3 4，2，3，1 4，1，2，3

通过end1和end2端混合输出，可以输出这10种中的8种，见表3-1。其中，S_L、X_L分别代表end1端的进队和出队，X_R代表end2端的出队。

表3-1 通过end1和end2端的混合输出序列（输入受限）

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

再看输出受限的双端队列，如图3-8所示。假设end1端和end2端都能输入，仅end2端可以输出。如果都从end2端输入，从end2端输出，就是一个栈了。当输入序列为1，2，3，4时，输出序列有14种。对于其他10种不能输出的序列，通过交替从end1和end2端输入，还可以输出其中8种。设S_L代表end1端的输入，S_R、X_R分别代表end2端的输入和输出，则可能的输出序列及进队和出队顺序见表3-2。通过输出受限的双端队列不能输出的两种序列是：4，1，3，2和4，2，3，1。

表3-2 输出受限的双端队列

综上所述可得：

能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列是4，1，3，2；能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列是4，2，1，3；既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是4，2，3，1。