数据结构第八弹---队列

1、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性
表，队列具有先进先出FIFO(First In First Out) 的原则。

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头。

如何实现队列？
队列是一种一端插入一端删除的数据结构，所以最好的实现方式是头删尾插效率高或者头插尾删效率高。

1.数组实现：尾插和尾删效率较高，不太适合。
2.单链表实现：头删尾插效率较高，链表头删，链表尾插。
前面单链表提到尾插之前需要找到尾结点，为什么此处又说尾插效率高呢？
因为我们可以在定义结构的时候创建一个记录尾结点的变量，这样我们每次尾插的时候就不需要找尾结点了。
3.双向链表实现：头插头删尾插尾删效率都较高，可以实现队列。
双向链表头插头删尾插尾删效率都较高，为什么此处不直接使用双向链表实现呢？
因为单链表就能很好的实现一个队列，而双向链表相较与单链表会多开辟一个结点，在空间方面会有更多的消耗，所以一般不推荐使用双向链表实现队列。

2、队列的实现

经过上述的分析，我们推荐使用单链表实现队列，那么接下来就由博主来实现一下队列。

首先创建一个工程。(下图为vs 2022)

Queue.h（队列的类型定义、接口函数声明、引用的头文件）
Queue.c（队列接口函数的实现）
test.c （主函数、测试顺序表各个接口功能）

2.1、头文件包含和结构定义

以下是实现队列可能用到的头文件。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

以下是博主创建的队列结构，可以根据自己的喜好创建喔。
建议：创建结构时最好能通俗易懂，最好不用拼音创建。

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next; //存放下一个结点指针
	QDataType data;         //存放数据
}QueueNode;

typedef struct Queue
{
	QueueNode* head;//头结点
	QueueNode* tail;//尾结点
}Queue;

2.2、初始化

链表的结构是通过动态开辟的空间，可以先不初始化。但是队列的结构是在栈区开辟的，为了防止越界访问，需要先初始化为NULL。

void QueueInit(Queue* pq)
{
	assert(pq);//防止空指针传入
	pq->head = pq->tail = NULL;//初始化为空指针，防止野指针问题
}

2.3、销毁

队列是通过动态开辟的内存，需要手动释放，即依次遍历将结点空间释放，并手动置空。
思想：定义一个变量用来找结点，不为空则释放然后找下一个结点，为空则结束。

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;//养成创建变量习惯，为了后面能找到头结点
	while (cur)
	{
		QueueNode* next = cur->next;//标记下一个结点
		free(cur);
		cur = next;//更新结点
	}
	pq->head = pq->tail = NULL;//释放完手动置NULL
}

2.4、判断是否为空

根据队列的初始化函数可知，在创建之前会将头结点置空，所以头结点为空则队列为空。

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//头结点为空则返回真
}

测试

2.5、入队

入队：即在队尾处插入数据。

画图分析如下

代码实现

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)//动态开辟后记得判断喔！
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)//没有数据情况
	{
		pq->head = pq->tail = newnode;//将新结点赋值给头尾结点
	}
	else//有数据情况
	{
		pq->tail->next = newnode;//尾结点下一个插入数据
		pq->tail = newnode;//将尾结点更新
	}
}

测试

2.6、出队

出队：即在队头位置删除数据。
前提：有数据才能出队

代码实现

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//确保有数据
	//一个元素
	if (pq->head->next == NULL)
	{
		free(pq->head);//释放空间
		pq->head = pq->tail = NULL;//手动置空
	}
	//多个元素
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);//释放空间
		pq->head = next;//更新头结点
	}
}

测试

队头元素就是头结点中存储的数据

2.7、获取队头数据

队头数据：即头结点数据。

代码实现

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

测试

2.8、获取队尾数据

队尾元素就是队尾结点的数据

代码实现

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

测试

将队列遍历一遍，计算大小

2.9、获取有效数据个数

有效数据个数：即有效结点个数。
思想：从头结点开始计算，不为空则size++，然后更新到下一个结点，为空则结束。

代码实现

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

测试

3、代码汇总

以下是Queue.h的代码。

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;//头结点
	QueueNode* tail;//尾结点
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//队头元素
QDataType QueueFront(Queue* pq);
//队尾元素
QDataType QueueBack(Queue* pq);
//计算大小
int QueueSize(Queue* pq);
//判断是否为空
bool QueueEmpty(Queue* pq);

以下是Queue.c的代码

#define _CRT_SECURE_NO_WARNINGS

#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("QueueNode fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

总结

本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！