数据结构之队列

片头

嗨,小伙伴们,大家好! 在上一篇中,我们学习了栈,那么在这一章中我们将学习队列的相关知识,准备好了吗 ? Ready Go ! ! !

一、队列

1.1 队列的基本概念

在上一章中，我们学习了数据结构之栈,知道了栈遵循后进先出(LIFO)原则。与栈相对的，队列中的数据元素遵循先进先出(FIFO)原则。那么什么是队列呢？

字面意思来看，就是下图中小狗们排队的场景，每当新的小狗想加入队列时，就会排到最后面；如果最前面的小狗打完饭了，就会出队列。也就是我们说的先进先出（FIFO）。

那么，在我们数据结构当中，队列的定义是什么？

队列： 只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出(FIFO)的特点。进行插入操作（入队）的一端称为队尾，进行删除操作（出队）的一端称为队头。

1.2 队列的实现

我们可以使用数组结构或链表结构来实现队列。如果使用数组来实现队列的话，数组的头插头删需要对每一个元素进行移动操作，效率不如链表。所以二者取其优，我们使用链表的结构实现队列会更简便高效。

关于链表，我们在前面已经学习过了数据结构之单链表和数据结构之双向循环链表，在这里，我们使用单链表就可以解决问题。

---

二、队列的接口实现 

我们先创建一个头文件“Queue.h”和2个源文件"Queue.c"和"Test.c",具体作用为:

明确了使用单链表后,我们需要考虑更多的细节问题。出队的时候，由于队列的先进先出原则，我们要删除队头（即链表头结点） 所以需要一个指针来保存头结点的地址；而入队的时候，我们则需要从队尾（即链表尾结点）插入元素，所以还需要一个指针来保存尾结点的地址。综上所述，我们需要定义2个结构体：①队列中每一个结点的结构体（包含数据域，指针域）②队列结构体（front指针,rear指针,size表示队列的长度）(第2个结构体来保存头尾结点的地址)。

我们先展示“Queue.h”的完整代码,最后再展示"Queue.c"的完整代码。不要忘记在两个源文件中引用“Queue.h”

#pragma once			  //防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int ElemType;	   //如果要修改存储的数据类型可直接在此修改
typedef struct QListNode   //链式结构: 表示队列结点
{
	ElemType data;		   //每一个结点的数据域
	struct QListNode* next;//每一个结点的指针域
}QNode;
 
typedef struct Queue	   //队列的结构
{
	QNode* front;			//指向队头
	QNode* rear;			//指向队尾
}Queue;
 
//队列的增删查改接口实现(因为指针在结构体中,所以不需要传二级指针)
 
void QueueInit(Queue* q);//初始化队列
 
void QueuePush(Queue* q, ElemType x);//队尾入队列
 
void QueuePop(Queue* q);//队头出队列
 
ElemType QueueFront(Queue* q);//获取队列头部元素
 
ElemType QueueBack(Queue* q);//获取队列队尾元素
 
int QueueSize(Queue* q);//获取队列中有效元素个数
 
int QueueEmpty(Queue* q);//检测队列是否为空,如果为空返回非零结果,如果非空返回0
 
void QueueDestroy(Queue* q);//销毁队列

接下来我们开始逐个实现各个接口函数

（1）初始化队列

//初始化队列
void QueueInit(Queue* q) {
	assert(q);		 //断言,防止传入空指针
	q->front = NULL; //初始化指向头结点的指针
	q->rear = NULL;  //初始化指向尾结点的指针
	q->size = 0;	 //初始化队列的大小为0
}

（2）队尾入队列

//队尾入队列
void QueuePush(Queue* q, ElemType x) {
	assert(q);//断言,防止传入空指针
	QNode* newNode = (QNode*)malloc(sizeof(QNode));//创建新结点
	if (newNode == NULL) //如果空间开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;	 //新结点的数据域为x
	newNode->next = NULL;//新结点的指针域为NULL
 
	if (q->front == NULL) //q->front == NULL,说明队列为空
	{
		q->front = q->rear = newNode;//两个指针都指向新结点
	}
	else				  //如果队列不为空
	{
		q->rear->next = newNode;//原来的尾结点指向新结点
		q->rear = newNode;//新结点变成尾结点
	}
	q->size++;//队列的长度加1
}

因为队列和顺序表、链表不一样，它不能像链表遍历打印，需要使用 QueueEmpty函数 和 QueuePop函数, 后面会讲到。

（3）队头出队列

//队头出队列
void QueuePop(Queue* q) {
	assert(q);	//断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	if (q->front->next == NULL) //如果队列中只剩下1个结点
	{
		free(q->front);//释放唯一结点
		q->front = q->rear = NULL;//两个指针置空
	}
	else
	{
		//队列不止1个结点
		QNode* del = q->front;//用del临时变量保存头结点的地址
		q->front = del->next; //头结点更新
		free(del);			  //释放原来的头结点
		del = NULL;			  //置空
	}
	q->size--;			  //更新size
}

（4）获取队列头部元素

//获取队列头部元素
ElemType QueueFront(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	return q->front->data;//返回队头元素
}

（5）获取队列队尾元素

//获取队列队尾元素
ElemType QueueBack(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->rear != NULL);//断言,队列为空则报错
	return q->rear->data;//返回队尾元素
}

（6）获取队列中有效元素的个数

//获取队列中有效元素个数
int QueueSize(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size;		//size即为有效元素个数
}

（7） 检测队列是否为空

///检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size == 0;//如果为空返回1,如果非空返回0
}

（8）销毁队列

//销毁队列
void QueueDestroy(Queue* q) {
	assert(q);		    //断言,防止传入空指针
	QNode* p = q->front;//创建一个指针变量用来保存每次的头结点位置
	while (p != NULL)   //当 p == NULL时队列销毁完毕,跳出循环
	{
		QNode* Q = p->next;//更新头结点的地址
		free(p);		   //释放原来的头结点
		p = Q;			   //p指向新的头结点
	}
	q->front = q->rear = NULL;//将2个指针置空
	q->size = 0;//更新size
}

所有接口已经实现，我们在Test.c文件中测试一下:

哈哈哈,运行结果正确 ! 恭喜你,完成了实现队列的代码~ 下面是"Queue.c"文件的完整代码:

#include"Queue.h"
//队列的增删查改接口实现(因为指针在结构体中,所以不需要传二级指针)
 
//初始化队列
void QueueInit(Queue* q) {
	assert(q);		 //断言,防止传入空指针
	q->front = NULL; //初始化指向头结点的指针
	q->rear = NULL;  //初始化指向尾结点的指针
	q->size = 0;	 //初始化队列的大小为0
}
 
//队尾入队列
void QueuePush(Queue* q, ElemType x) {
	assert(q);//断言,防止传入空指针
	QNode* newNode = (QNode*)malloc(sizeof(QNode));//创建新结点
	if (newNode == NULL) //如果空间开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;	 //新结点的数据域为x
	newNode->next = NULL;//新结点的指针域为NULL
 
	if (q->front == NULL) //q->front == NULL,说明队列为空
	{
		q->front = q->rear = newNode;//两个指针都指向新结点
	}
	else				  //如果队列不为空
	{
		q->rear->next = newNode;//原来的尾结点指向新结点
		q->rear = newNode;//新结点变成尾结点
	}
	q->size++;//队列的长度加1
}
 
//队头出队列
void QueuePop(Queue* q) {
	assert(q);	//断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	if (q->front->next == NULL) //如果队列中只剩下1个结点
	{
		free(q->front);//释放唯一结点
		q->front = q->rear = NULL;//两个指针置空
	}
	else
	{
		//队列不止1个结点
		QNode* del = q->front;//用del临时变量保存头结点的地址
		q->front = del->next; //头结点更新
		free(del);			  //释放原来的头结点
		del = NULL;			  //置空
	}
	q->size--;			  //更新size
}
 
//获取队列头部元素
ElemType QueueFront(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->front != NULL);//断言,队列为空则报错
	return q->front->data;//返回队头元素
}
 
//获取队列队尾元素
ElemType QueueBack(Queue* q) {
	assert(q);			 //断言,防止传入空指针
	assert(q->rear != NULL);//断言,队列为空则报错
	return q->rear->data;//返回队尾元素
}
 
//获取队列中有效元素个数
int QueueSize(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size;		//size即为有效元素个数
}
 
//检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q) {
	assert(q);			//断言,防止传入空指针
	return q->size == 0;//如果为空返回1,如果非空返回0
}
 
//销毁队列
void QueueDestroy(Queue* q) {
	assert(q);		    //断言,防止传入空指针
	QNode* p = q->front;//创建一个指针变量用来保存每次的头结点位置
	while (p != NULL)   //当 p == NULL时队列销毁完毕,跳出循环
	{
		QNode* Q = p->next;//更新头结点的地址
		free(p);		   //释放原来的头结点
		p = Q;			   //p指向新的头结点
	}
	q->front = q->rear = NULL;//将2个指针置空
	q->size = 0;//更新size
}

片尾

今天我们学习了什么是队列以及如何实现队列等问题,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !