【数据结构】队列详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】队列详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

☃️个人主页：fighting小泽
🌸作者简介：目前正在学习C语言和数据结构
🌼博客专栏：数据结构
🏵️欢迎关注：评论👊🏻点赞👍🏻留言💪🏻

1.队列

1.1队列的概念及结构

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

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
【数据结构】队列详解

比如说我们要将1、2、3、4这几个数进行入队列和出队列的操作

我们发现入队列的顺序是1、2、3、4，出队列的顺序也是1、2、3、4。
要是我们先入1、2两个数据，并让它们出队列，然后再入3、4两个数据，再让它们出队列，我们发现出队列的顺序还是1、2、3、4。
所以队列的特性就是先入先出，并且顺序不会因为出数据而改变。

那么队列在我们生活中有什么用处呢？

举个例子：我们平时去餐厅买饭的时候会先排队，点完餐之后老板会给你一个号，等叫到你的号时便可以去领自己的饭菜了。所以通过队列我们就可以实现一个抽号机，先来的人会先领到号，而且凭号领饭，不会被别人插队。这是不是队列的先入先出性质在我们生活中的应用。

1.2队列的实现

队列也可以通过数组或者链表来实现，但是哪种方式更好呢？

我们想一想，队列每次都是在队尾入数据，在队头出数据。是不是会经常用到尾插和头删操作。
我们知道数组进行头插操作需要移动整个数组的元素，效率很低。虽然数组尾插很方便，但总体还是弊大于利的。所以我们用链表实现会比较好一点。

我们知道链表进行头插操作很容易，但是进行尾插操作却需要遍历一遍链表，那有没有好的解决办法呢？

有的！我们可以专门用一个指针记录下尾节点的位置，然后在尾节点后面进行尾插操作，再改变尾节点的位置即可。

1.2队列的结构

由于队列是由链表构成的，所以链表的每个节点存储了一个数据和指向下一个链表的指针。
注意：这里传的都是结构体的地址，是形参，最好用assert断言一下。不可以改变结构体，但是可以改变结构体的元素。

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

由于队列要进行尾插头删操作，所以我们可以再定义一个结构体来保存队列的头指针和尾指针。队列的大小最好也保存一下。因为我们想要进行入队列出队列操作时，只需要通过队列的头指针和尾指针就可以进行尾插头删操作。
头插不用二级指针的方式：

1.用返回值
2.将指针放在结构体中

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

很多人可能疑惑为什么要定义两个结构体。注意结构体的定义是根据我们的需求来定的，不要被固定的思维限制住了。【数据结构】队列详解

Queue.h

#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;

}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

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

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

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

QDataType QueueFront(Queue* pq);//获得队列的第一个元素

QDataType QueueBack(Queue* pq);//获得队列的最后一个元素

int QSize(Queue* pq);//获得队列的元素个数

bool QueueEmpty(Queue* pq);//判断队列是否为空

Queue.c

1.初始化和销毁队列

队列初始化的时候我们可以先给它开辟一些空间，也可以等使用时再开辟，这里我就不开辟啦。初始化就把它的指针置空，把大小置为0就行。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

队列的销毁跟链表相同，每次记录下头节点下一个节点的位置，再把头节点释放掉，直到释放完为止。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	while (pq->phead)
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

2.入队列操作

入队列要分为两种情况

若队列为空，我们要把尾指针和头指针都指向要插入的新节点
若队列不为空，我们直接通过尾指针进行尾插就行了。
注意入队列时size要+1

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	newnode->data = x;
	newnode->next = NULL;
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	else
	{
		if (pq->phead == NULL)
		{
			assert(pq->ptail == NULL);//都为空
			pq->phead = pq->ptail = newnode;
		}
		else
		{
			pq->ptail->next = newnode;
			pq->ptail = newnode;
		}

		pq->size++;
	}
}

3.出队列操作

同样，出队列也要分为多种情况：

若队列为空，我们就不能进行出队列操作了，我们可以写一个QueueEmpty函数来判断队列是否为空
若队列有多个元素，我们只需要将头指针指向下一个节点，然后释放掉原来的头节点即可。
若队列只有一个元素，我们要是还按第二种方式的话，头节点就指向了NULL，队列就没有元素了，而尾节点却还指向原来的节点。这时尾节点是不是就成为了一个尾指针了，所以要把它给置空，

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		pq->size = 0;
	}
	else
	{
		QNode* tmp = pq->phead->next;
		free(pq->phead);
		pq->phead = tmp;
		pq->size--;
	}
}

4.判断队列是否为空和获得队列元素个数

判断队列为空，只需要看它的大小是不是为0就行，或者判断队列的头指针和尾指针是不是都是空指针。

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

获得队列的元素个数，很简单，只需要返回队列的size就行

int QSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

5.获得队列头、尾元素

注意元素队列空我们就不能获得元素了，所以要assert判断一下。
然后直接返回头尾指针指向节点存储的data数据即可。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}