作者：解学武

队列，可以理解为遵循“先进先出”原则的线性表，即数据元素依次从表的一端进，从表的另一端出。

链队列，即用链式的存储结构（链表）实现的队列，其实现思想是：用链表的表头一端表示队列的队头，另一端表示队列的队尾（实现代码更加简单）。

反过来的话，当队列增加元素时，要采用头插法，在删除数据元素的时候，需通过遍历的方式摘除链表的最后一个结点。

需要注意的是，在实现链队列时要合理地控制队列两端指针的指向，避免“野指针”的出现。例如，当链队列中只剩有一个数据元素时，队尾指针指向的就是这个数据元素，被删除后，队尾指针指向的内存空间被释放，还有可能给别的程序使用。这时候，队尾指针如果不进行重定义，就会变成“野指针”。

链队列的实现代码如下：

#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){
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //使用尾插法向链队列中添加数据元素
    rear->next=enElem;
    rear=enElem;
    return rear;
}
void DeQueue(QNode * front,QNode * rear){
    if (front->next==NULL) {
        printf("队列为空");
        return ;
    }
    QNode * p=front->next;
    printf("%d",p->data);
    front->next=p->next;
    if (rear==p) {
        rear=front;
    }
    free(p);
}
int main() {
    QNode * queue,*front,*rear;
    queue=front=rear=initQueue();//创建头结点
    //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
    DeQueue(front, rear);
    return 0;
}

运行结果：
1234队列为空
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。