【数据结构初阶第十节】队列（详解+附源码）

好久不见。。。别不开心了，听听喜欢的歌吧

必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客

一、概念和结构

二、队列的实现

Queue.h

Queue.c

test.c

Relaxing Time！

————————————《有没有那么一首歌会让你想起我》————————————

这节课我们学习队列的概念和结构以及实现，需要提前具备前面顺序表和链表的相关知识，这样这节课就会变得非常简单！

一、概念和结构

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

入队列： 进行插⼊操作的⼀端称为队尾。

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

队列底层结构选型： 队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队列在数组头上出数据，效率会⽐较低。

下图解释为什么用链表来实现队列

二、队列的实现

Queue.h

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

//创建节点的结构
typedef int QUDatatype;
typedef struct QueueNode
{
	QUDatatype data;
	struct QueueNode* next;
}QueueNode;

//创建队列的结构
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;//队列里面有效数据个数
}Queue;

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

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

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

//取队头数据
QUDatatype QueueFront(Queue* pq);

//取队尾数据
QUDatatype QueueBack(Queue* pq);

//取队列有效元素个数
int QueueSize(Queue* pq);

//销毁
void QueueDestroy(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,QUDatatype x)
{
	assert(pq);
	//申请一个新的结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail！");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	++pq->size;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//下面这样写也ok，return pq->phead == NULL && pq->ptail == NULL ;
	return pq->phead == NULL;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	
	//若只有一个结点,防止ptail成为野指针
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//删除对头元素
		QueueNode* Next = pq->phead->next;
		free(pq->phead);
		pq->phead = Next;
	}
	--pq->size;
}

//取队头数据
QUDatatype QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->phead->data;

}

//取队尾数据
QUDatatype QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}

//取队列有效元素个数,时间复杂度为O(N),我们可以优化一下
//我们可以增加一个变量size去记录队列里面有效数据的个数然后直接返回
int QueueSize(Queue* pq)
{
	assert(pq);
	/*QueueNode* pcur = pq->phead;
	int count = 0;
	while (pcur)
	{
		count++;
		QueuePop(pq);
		pcur = pq->phead;
	}*/
	/*return count;*/

	return pq->size;
}

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//针对队列里面的结构进行销毁
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

test.c

#include"Queue.h"

void test()
{
	Queue pq;
	QueueInit(&pq);
	QueuePush(&pq, 1);
	QueuePush(&pq, 2);
	QueuePush(&pq, 3);
	QueuePush(&pq, 4);

	/*QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);
	QueuePop(&pq);*/

	printf("head:%d\n", QueueFront(&pq));
	printf("back:%d\n", QueueBack(&pq));

	//两种 取队列里面有效数据的个数 方法
	printf("队列里面有效数据个数为：%d \n",QueueSize(&pq));
	printf("size:%d\n", QueueSize(&pq));
	printf("size:%d\n", pq.size);

	QueueDestroy(&pq);

}

int main()
{
	test();
	return 0;
}

实现队列需要注意的比较重要的点见下

取队列里面有效数据的个数，如果用老方法套路实现时间复杂度为O(N)，但是我们可以在队列里面重新定义一个结构，size来记录，每次入数据，出数据直接调整size即可，取有效数据个数的时候直接返回 size 就简单了很多。
在队列销毁的时候，不要忘记最后把队列结构里面的phead和ptail指针置为NULL，size == 0。
我们定义了ptail指针，指向队尾，可以直接找到队尾入数据。

经过前几节顺序表，单链表，双链表，栈的学习，今天学习队列真是游刃有余呦，下一节是栈和队列的算法题，期待一下啦~~

完——