[数据结构与算法]数据结构学习笔记——链式存储结构实现队列（链队）

一、链队

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

在链队中，队头指针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; 
} 

注：在出队操作中，假设只有三个数据元素的带头结点的链队（不带头结点也是一样），执行出队操作，若只出队一个或两个数据元素则只需修改队头指针，而若所有元素都要出队则此时队头和队尾指针都变为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);	//遍历输出队列
}

运行结果如下：