一、链队

链队是通过带有队头指针和队尾指针的单链表实现的，使用链队的好处是可以避免出现队列满且溢出的问题，且适用于数据元素变动较大的情形时。

在链队中，队头指针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);  //遍历输出队列
}

运行结果如下：

数据结构学习笔记——链式存储结构实现队列（链队）