【数据结构初阶】--栈和队列(二)

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言： 在上篇博客中我们简单完成了栈这个数据结构的实现，那么这次我们要实现的是队列，队列这个数据结构实现起来也不会很难，还是和之前一样，先部分实现，最后展现全部的代码 

目录

一.队列的概念与结构

二. 队列的入队和出队

入队：

 出队：

 三.队列取队首数据和队尾数据

取队首数据：

取队尾数据 ：

 四.队列的有效数据个数和队列的销毁

队列的有效数据个数：

销毁队列：

五.代码展现

Queue.h：

Queue.c：

test.c：

一.队列的概念与结构

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

入队列：进行插入操作的一端称为队尾

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

 队列底层结构选型：

队列可以用数组和链表的结构实现，使用链表的结构实现更优一点，如果使用数组的结构，出队列在数组头部出数据，时间复杂度高。虽然使用链表在入队尾插的时候，时间复杂度也高，但我们可以额外定义一个尾结点，这样就可以优化了

结构定义： 

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

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size;//队中有效数据个数
}Queue;

二. 队列的入队和出队

--我们实现队列的入队是在队尾操作的，所以我们可以参考链表的尾插，但是这里我们已经定义了一个尾节点了，所以会更简单点

入队：

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newcode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;

	//如果队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newcode;
		//pq->size++;
	}
	else
	{
		pq->ptail->next = newcode;
		pq->ptail = pq->ptail->next;
		//pq->size++;
	}
}

我们入队之前，需要申请一个新的节点，操作起来和链表里面的一样，申请完后先判断链表是不是为空，为空和不为空需要分类讨论，如果为空就直接令头节点和尾节点都为newcode，如果不为空就是在尾节点后链接上新节点，然后尾节点往前走。 

 --在实现出队之前，我们需要考虑到一个队列为空的问题，如果队列为空是不是就不能删了呢，所以我们这里来实现一个判断链表是否为空的接口吧，这个实现起来很简单，就不多说了

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

 出队：

//出队
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//如果队伍中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		//pq->size--||pq->size=0
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		//pq->size--;
	}
}

我们需要注意的是断言结束后，如果队伍只有一个节点，我们直接释放掉后使置为空就行了，如果不止一个节点我们需要先记录下一个节点，再释放，然后让头节点来到下一个节点的位置。

 三.队列取队首数据和队尾数据

取队首数据：

//取队首数据
QDataType QueueHead(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

队首数据不就是头节点的数据吗，直接返回就好了

取队尾数据 ：

//取队尾数据
QDataType QueueTail(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

队尾数据不就是头节点的数据吗，直接返回就好了

--实现完前面的接口之后我们可以测试一下看看

 test.c：

#include"Queue.h"

void test1()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	printf("队首是:%d\n",QueueHead(&q));
	printf("队尾是:%d\n",QueueTail(&q));
}

int main()
{
	test1();
}

--测试完成，打印出了队尾和队首数据，退出码为0

 四.队列的有效数据个数和队列的销毁

队列的有效数据个数：

//队列有效数据个数
int QueueSize(Queue* pq)
{
	//如果使用了size记录直接返回就可以了
	//return pq->size;

	//如果没有就遍历
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur=pcur->next;
	}
	return size;
}

这里给大家提供了两种写法，一个是前面定义了size的，一个是没有定义过的，没有定义的我们需要遍历计数，最后再返回就行了。 

销毁队列：

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}

遍历队列，每次销毁前存下下一个节点，销毁当前节点后来到下一个节点的位置，最后遍历结束后把pq->phead和pq->ptail都置为空

--这里也可以通过测试文件打印观察数据个数，就不在这里展示了，大家可以直接看一下代码展现里面 

五.代码展现

Queue.h：

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

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

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size;//队中有效数据个数
}Queue;

//队列的初始化
void QueueInit(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);

//队列判空
bool QueueEmpty(Queue* pq);

//出队
void QueuePop(Queue* pq);

//取队首数据
QDataType QueueHead(Queue* pq);

//取队尾数据
QDataType QueueTail(Queue* pq);

//队列有效数据个数
int QueueSize(Queue* pq);

//队列的销毁
void QueueDestory(Queue* pq);

Queue.c：

#include"Queue.h"

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	//pq->size = 0;
}

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newcode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;

	//如果队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newcode;
		//pq->size++;
	}
	else
	{
		pq->ptail->next = newcode;
		pq->ptail = pq->ptail->next;
		//pq->size++;
	}
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

//出队
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//如果队伍中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		//pq->size--||pq->size=0
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		//pq->size--;
	}
}

//取队首数据
QDataType QueueHead(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队尾数据
QDataType QueueTail(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

//队列有效数据个数
int QueueSize(Queue* pq)
{
	//如果使用了size记录直接返回就可以了
	//return pq->size;

	//如果没有就遍历
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur=pcur->next;
	}
	return size;
}

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}

test.c：

#include"Queue.h"

void test1()
{
	Queue q;
	QueueInit(&q);

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	printf("队首是:%d\n",QueueHead(&q));
	printf("队尾是:%d\n",QueueTail(&q));
	printf("size:%d\n", QueueSize(&q));

	QueueDestory(&q);
}

int main()
{
	test1();
}

往期回顾：

【数据结构初阶】--双向链表(一)

【数据结构初阶】--双向链表(二)

【数据结构初阶】--栈和队列(一)

结语：队列的实现就到此结束了，栈和队列这块的知识点和实现起来都比较快，但是后面的二叉树的难度就上来了，大家一定要先把前面这些搞懂并且实现出来，不然后续会比较吃力的，如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持