一、链队
链队是通过带有队头指针和队尾指针的单链表实现的，使用链队的好处是可以避免出现队列满且溢出的问题，且适用于数据元素变动较大的情形时。
在链队中，队头指针Q.front指向队头结点，队尾指针Q.rear指向队尾结点，由于不带头结点的链队操作较为麻烦，一般将链队设置为带头结点的单链表，带头结点的链式队列如下图（其中队头指针指向头节点）：
不带结点的链式队列如下图：
以下代码的实现均为在带头结点的链式队列中操作。
二、链队的定义
链队的存储类型可定义为：
//链式队列的定义 typedef struct LinkNode { //链式队列的结点类型 int data; //结点的数据域 struct LinkNode *next; //结点的指针域 } LinkNode; typedef struct { //链式队列 LinkNode *front,*rear; //链式队列的队头指针和队尾指针 } LinkQueue;
三、链队的初始化
初始化时，通过malloc()函数创建一个只包含头结点的空链式队列Q，该头结点中包含队头指针front和队尾指针rear，然后将它们的指针域都指向空（NULL），代码如下：
//链式队列的初始化 void InitQueue(LinkQueue &Q) { Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); //建立头结点 Q.front->next=NULL; //初始化为空 }
四、判断链队是否为空队
判断链队是否为空，只需判断Q.front==Q.rear即可，代码如下：
//判断链式队列是否为空队 bool EmptyQueue(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }
由于通过链式存储实现队列，就不会存在容量的限制，所以不用考虑队列是否为满队。
五、入队（插入操作）
入队的操作是在队尾进行的，首先创建一个新结点s，赋给其数据域x值，并将其指针域置为空，之后将其插入到队列的末尾，最后再将队尾指针指向该结点，如下图：
实现代码如下：
//入队操作 void EnterQueue(LinkQueue &Q,int x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); //创建一个新结点s s->data=x; //传入新结点s的数据域x值 s->next=NULL; //设置新结点s的指针域为空 Q.rear->next=s; //将新结点s插入至当前链队末尾 Q.rear=s; //队尾指针指向新结点s }
六、出队（删除操作）
出队的操作是在队头进行的，首先判断队列是否为空，由于是带头结点的链队（其队头指针front指向头结点而不是第一个数据元素），设置一个指针p指向队头元素，并通过x变量将该结点存放的值取出，然后将队头指针指向下一个元素（新队头元素），此时还要判断是否队列中除了头节点外只有一个结点，因为此时出队后队列为空，判断成立后将队尾指针指向队头指针，然后再释放结点即可完成出队操作，如下图：
实现代码如下：
//出队操作 bool PopQueue(LinkQueue &Q,int &x){ if(Q.front==Q.rear) //判断是否为空队 return false; LinkNode *p=Q.front->next; //指针p指向队头元素 x=p->data; //取出队头元素并赋值给x Q.front->next=p->next; //队头指针的指针域存放在新队头元素的地址（下一个元素） if(Q.rear==p) //若队列中只存在一个结点时，出队后队列变空 Q.rear=Q.front; //队尾指针指向队头指针 free(p); //释放结点 return true; }
删除元素是从表头删除的，通常只需要修改头指针，但若队列中仅有一个元素时，则尾指针也需要修改，即当只有一个元素时，删除后队列为空，尾指针应修改为Q.rear=Q.front。
注：在出队操作中，假设只有三个数据元素的带头结点的链队（不带头结点也是一样），执行出队操作，若只出队一个或两个数据元素则只需修改队头指针，而若所有元素都要出队则此时队头和队尾指针都变为NULL，即此时队头和队尾都被修改。
七、读取链队的队头元素
首先判断队列是否为空，然后通过x取出第一个元素（队头指针原本是指向头结点的），代码如下：
//读取链队的队头元素 bool GetHeadQueue(LinkQueue Q,int &x) { if(Q.front==Q.rear) //判断是否为空队 return false; x=Q.front->next->data; return true; }
八、链队的遍历输出
首先判断队列是否为空，这里运用到正确单链表的依次输出各元素的代码，即通过设置一个指针p，使其指向头结点的next域，即指向第一个数据元素，经过while()循环输出每次p指针的数据域（p最终不为空时输出每个结点的数据域），然后依次先后移动p指针，从而输出单链表的所有数据元素，代码如下：
//链队的遍历输出 bool PrintQueue(LinkQueue Q,int x) { if(Q.front==Q.rear) //判断是否为空队 return false; LinkNode *p=Q.front->next; //指针p指向队头元素 while(p!=NULL) { printf("%d ",p->data); p=p->next; } return true; }
九、链队的建立
与先前的代码一样，通过输入一个值表示要创建的顺序队列的元素个数，然后通过一个for循环建立顺序队列，其中每次通过链式队列的入队操作，从而向队列中输入数据元素并依次插入至队列末尾，代码如下：
//链队的建立 void CreateQueue(LinkQueue &Q,int x) { int number; printf("请输入要建立的队列元素个数：\n"); scanf("%d",&number); for(int i=0; i<number; i++) { printf("输入第%d个入队的元素：\n",i+1); scanf("%d",&x); EnterQueue(Q,x); } }
❤️链队的完整代码
完整代码如下：
#include<stdio.h> #include<stdlib.h> //链式队列的定义 typedef struct LinkNode { //链式队列的结点类型 int data; //结点的数据域 struct LinkNode *next; //结点的指针域 } LinkNode; typedef struct { //链式队列 LinkNode *front,*rear; //链式队列的队头指针和队尾指针 } LinkQueue; //链式队列的初始化 void InitQueue(LinkQueue &Q) { Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); //建立头结点 Q.front->next=NULL; //初始化为空 } //判断链式队列是否为空队 bool EmptyQueue(LinkQueue Q) { if(Q.front==Q.rear) return true; else return false; } //入队操作 void EnterQueue(LinkQueue &Q,int x) { LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); //创建一个新结点s s->data=x; //传入新结点s的数据域x值 s->next=NULL; //设置新结点s的指针域为空 Q.rear->next=s; //将新结点s插入至当前链队末尾 Q.rear=s; //队尾指针指向新结点s } //出队操作 bool PopQueue(LinkQueue &Q,int &x) { if(Q.front==Q.rear) //判断是否为空队 return false; LinkNode *p=Q.front->next; //指针p指向队头元素 x=p->data; //取出队头元素并赋值给x Q.front->next=p->next; //队头指针的指针域存放在新队头元素的地址（下一个元素） if(Q.rear==p) //若队列中只存在一个结点时，出队后队列变空 Q.rear=Q.front; //队尾指针指向队头指针 free(p); //释放结点 return true; } //读取链队的队头元素 bool GetHeadQueue(LinkQueue Q,int &x) { if(Q.front==Q.rear) //判断是否为空队 return false; x=Q.front->next->data; return true; } //链队的遍历输出 bool PrintQueue(LinkQueue Q,int x) { if(Q.front==Q.rear) //判断是否为空队 return false; LinkNode *p=Q.front->next; //指针p指向队头元素 while(p!=NULL) { printf("%d ",p->data); p=p->next; } return true; } //链队的建立 void CreateQueue(LinkQueue &Q,int x) { int number; printf("请输入要建立的队列元素个数：\n"); scanf("%d",&number); for(int i=0; i<number; i++) { printf("输入第%d个入队的元素：\n",i+1); scanf("%d",&x); EnterQueue(Q,x); } }
一个简单的链队基本实现例子
例如，创建一个顺序队列，其初始数据为{1，2，3，4}，首先遍历输出该队列，然后读取队头元素，执行一次入队操作，入队元素为{5}，此时读取当前的队头元素，执行一次出队操作，此时再读取当前的队头元素，最后遍历输出当前队列。
代码如下：
#include<stdio.h> #include<stdlib.h> //链式队列的定义 typedef struct LinkNode { //链式队列的结点类型 int data; //结点的数据域 struct LinkNode *next; //结点的指针域 } LinkNode; typedef struct { //链式队列 LinkNode *front,*rear; //链式队列的队头指针和队尾指针 } LinkQueue; //链式队列的初始化 void InitQueue(LinkQueue &Q) { Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); //建立头结点 Q.front->next=NULL; //初始化为空 } //判断链式队列是否为空队 bool EmptyQueue(LinkQueue Q) { if(Q.front==Q.rear) return true; else return false; } //入队操作 void EnterQueue(LinkQueue &Q,int x) { LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); //创建一个新结点s s->data=x; //传入新结点s的数据域x值 s->next=NULL; //设置新结点s的指针域为空 Q.rear->next=s; //将新结点s插入至当前链队末尾 Q.rear=s; //队尾指针指向新结点s } //出队操作 bool PopQueue(LinkQueue &Q,int &x) { if(Q.front==Q.rear) //判断是否为空队 return false; LinkNode *p=Q.front->next; //指针p指向队头元素 x=p->data; //取出队头元素并赋值给x Q.front->next=p->next; //队头指针的指针域存放在新队头元素的地址（下一个元素） if(Q.rear==p) //若队列中只存在一个结点时，出队后队列变空 Q.rear=Q.front; //队尾指针指向队头指针 free(p); //释放结点 return true; } //读取链队的队头元素 bool GetHeadQueue(LinkQueue Q,int &x) { if(Q.front==Q.rear) //判断是否为空队 return false; x=Q.front->next->data; return true; } //链队的遍历输出 bool PrintQueue(LinkQueue Q,int x) { if(Q.front==Q.rear) //判断是否为空队 return false; LinkNode *p=Q.front->next; //指针p指向队头元素 while(p!=NULL) { printf("%d ",p->data); p=p->next; } return true; } //链队的建立 void CreateQueue(LinkQueue &Q,int x) { int number; printf("请输入要建立的队列元素个数：\n"); scanf("%d",&number); for(int i=0; i<number; i++) { printf("输入第%d个入队的元素：\n",i+1); scanf("%d",&x); EnterQueue(Q,x); } } int main() { LinkQueue Q; int x,e; InitQueue(Q); //初始化 CreateQueue(Q,x); //创建队列 printf("遍历输出当前队列元素：\n"); PrintQueue(Q,x); //遍历输出队列 printf("\n"); GetHeadQueue(Q,x); //读取队列的队头元素 printf("读取队列的队头元素,当前队头元素为：%d\n",x); printf("请输入一个要入队的元素："); scanf("%d",&e); EnterQueue(Q,e); //入队操作 GetHeadQueue(Q,x); printf("读取队列的队头元素,当前队头元素为：%d\n",x); PopQueue(Q,x); //出队操作 GetHeadQueue(Q,x); printf("执行一次出队操作后,当前队头元素为：%d\n",x); printf("遍历输出当前队列元素：\n"); PrintQueue(Q,x); //遍历输出队列 }
运行结果如下：
