作者：解学武

链式队列，简称"链队列"，即使用链表实现的队列存储结构。

链式队列的实现思想同顺序队列类似，创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素，如图 1 所示：
图 1 所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。

在创建链式队列时，强烈建议初学者创建一个带有头节点的链表，这样实现链式队列会更简单。

由此，我们可以编写出创建链式队列的 C 语言实现代码为：

//链表中的节点结构
typedef struct qnode{
    int data;
    struct qnode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
    //创建一个头节点
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next=NULL;
    return queue;
}

链式队列数据入队

链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：

1. 将该数据元素用节点包裹，例如新节点名称为 elem；
2. 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
3. 最后移动 rear 指针指向该新节点，即 rear=elem；

由此，新节点就入队成功了。

例如，在图 1 的基础上，我们依次将 {1,2,3} 依次入队，各个数据元素入队的过程如图 2 所示：

如图 2 中，我们将链表的头部作为队列的队头，将链表的尾部作为队列的队尾。当然，也可以反过来，将链表的头部（尾部）作为队列的队尾（队头），两种存储方式都可以。

数据元素入链式队列的 C 语言实现代码为：

QNode* enQueue(QNode * rear,int data){
    //1、用节点包裹入队元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next=enElem;
    //3、rear指向新节点
    rear=enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

链式队列数据出队

当链式队列中有元素需要出队时，按照 "先进先出" 的原则，需要先将在它之前入队的元素依次出队，然后该目标元素才能出队。

我们知道，队列中的元素只能从队头出队。在图 2 中，队列的队头位于链表的头部。因此队列中元素出队的过程，其实是链表中摘除首元结点的过程，需要做以下 3 步操作：

1. 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
2. 将 top 所指结点的 next 指针，指向 p 结点的直接后继结点；
3. 释放节点 p 占用的内存空间；

例如，在图 2b) 的基础上，我们将元素 1 和 2 出队，则操作过程如图 3 所示：
链式队列中队头元素出队的 C 语言实现代码为：

QNode* DeQueue(QNode* top, QNode* rear) {
    QNode* p = NULL;
    if (top->next == NULL) {
        printf("\n队列为空\n");
        return rear;
    }
    // 1、创建新指针 p 指向目标结点
    p = top->next;
    printf("%d ", p->data);
    //2、将目标结点从链表上摘除
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    //3、释放结点 p 占用的内存
    free(p);
    return rear;
}

注意，将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。此外，程序中要判断被摘除的目标结点是否是 rear 队头队尾，如果是的话，要及时更新 rear 指针的指向。

总结

通过学习链式队列最基本的数据入队和出队操作，我们可以就实际问题，对以上代码做适当的修改。

前面在学习顺序队列时，由于顺序表的局限性，我们在顺序队列中实现数据入队和出队的基础上，又对实现代码做了改进，令其能够充分利用数组中的空间。链式队列就不需要考虑空间利用的问题，因为链式队列本身就是实时申请空间。因此，这可以算作是链式队列相比顺序队列的一个优势。

这里给出链式队列入队和出队的完整 C 语言代码为：

#include <stdio.h>
#include <stdlib.h>
//链表中的节点结构
typedef struct qnode {
    int data;
    struct qnode* next;
}QNode;
//创建链式队列的函数
QNode* initQueue() {
    //创建一个头节点
    QNode* queue = (QNode*)malloc(sizeof(QNode));
    //对头节点进行初始化
    queue->next = NULL;
    return queue;
}

QNode* enQueue(QNode* rear, int data) {
    //1、用节点包裹入队元素
    QNode* enElem = (QNode*)malloc(sizeof(QNode));
    enElem->data = data;
    enElem->next = NULL;
    //2、新节点与rear节点建立逻辑关系
    rear->next = enElem;
    //3、rear指向新节点
    rear = enElem;
    //返回新的rear，为后续新元素入队做准备
    return rear;
}

QNode* deQueue(QNode* top, QNode* rear) {
    QNode* p = NULL;
    if (top->next == NULL) {
        printf("\n队列为空\n");
        return rear;
    }
    // 1、创建新指针 p 指向目标结点
    p = top->next;
    printf("%d ", p->data);
    //2、将目标结点从链表上摘除
    top->next = p->next;
    if (rear == p) {
        rear = top;
    }
    //3、释放结点 p 占用的内存
    free(p);
    return rear;
}

int main() {
    QNode* queue = NULL, * top = NULL, * rear = NULL;
    queue = top = rear = initQueue();//创建头结点
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear = enQueue(rear, 1);
    rear = enQueue(rear, 2);
    rear = enQueue(rear, 3);
    rear = enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    rear = deQueue(top, rear);
    return 0;
}

程序运行结果为：

1 2 3 4
队列为空