数据结构与算法 - 队列

文章目录

前言

路漫漫其修远兮，吾将上下而求索；

一、队列的概念及其结构

队列：只允许在一端(队头)进行插入数据的操作，在另外一端(队尾)进行删除数据操作的特殊线性表，并且队列具有先进先出(FIFO)的特点；

注：

• 先进先出 ，即FIFO : First In First Out
• 入队列：进行插入数据的那一端称为队尾
• 出队列：进行删除数据的那一端称为队头

与栈不相同的是，队列中的数据进入时是怎样的顺序那么出队列时便也是怎样的顺序；而栈会颠倒数据入栈时的顺序即后进先出；

注：上图仅作为形象标识队列如何出入数据，并不是在暗示你队列要使用数组来实现；

二、队列的实现

(一)、底层结构的选择

队列的实现可以选择两种结构： 1、数组   2、链表

我们先来分析一下队列是否可以用数组来实现，根据队列数据存放的特点：先进先出；

• 我们如果将下标为0处的空间当作队头，尾插时间复杂度为O(1),但是如果在队头出数据的话就得将下标为0往后的数据一个一个地往前挪动，时间复杂度为O(N)，消耗很大；
• 而如若我们将下标为0处的空间当作队尾，那么当入队列即插入数据时，就需要将所有数据均往后挪动一个空间，将下标为0的空间给空出来用来存放所要插入的数据，其时间复杂度为O(N)，显然消耗也很大；

故而，数组不适合用来实现队列；

• 若使用单链表，将尾结点当作队尾，头结点当作队头，出队列相当于头删，入队列相当于尾插，需要知道尾结点的地址；
• 倘若将头节点当作队尾，把尾结点当作队头，入队列相当于头插，出队列相当于尾删，需要尾结点和尾结点前一个结点的地址，稍微会麻烦一点；

既然均会使用到尾结点，我们可以再增加一个指向为尾结点的指针；

综上，我们使用单链表，将尾结点当作队尾，头结点当作队头；

队列 类型的声明：

上述结构体类型声明用图像展示便如下图所示：

(二)、Queue.h 的实现

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.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 QueueBack(Queue* pq);

//获取队头的数据
QDataType QueueFront(Queue* pq);

//队列中的数据个数
int QueueSize(Queue* pq);

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

//打印
void QueuePrint(Queue* pq);

(三)、Queue.c 的实现

1、初始化

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

}

2、销毁

//销毁
void QueueDestroy(Queue* pq)
{
	//释放所有动态开辟的空间
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//置空、置初始值
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

跟单链表结点的释放大体相同；

3、尾插

//尾插
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//插入数据前首先是要创建结点的空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//尾插需要分情况讨论结点的个数，当结点的个数为0时，便是头插
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//尾插
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

记得pst->size++;

4、头插

//头删
void QueuePop(Queue* pq)
{
	assert(pq);
	//首先是要确保有数据可以删除
	assert(pq->size);
	//删除:释放+处理链接关系
	QNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;

	pq->size--;

}

记得pst->size--;

5、获取队尾的数据

//获取队尾的数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//确保尾指针指向的结点不为空
	assert(pq->ptail);

	return pq->ptail->data;
}

在返回尾结点中的数据之前要确保 pst->ptail 不为NULL，以避免对NULL进行解引用操作；

6、获取队头的数据

//获取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//确保头指针指向的结点不为空
	assert(pq->phead);
	return pq->phead->data;
}

在返回头结点中的数据之前要确保 pst->phead 不为NULL，以避免对NULL进行解引用操作；

7、队列中的数据个数

//队列中的数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

8、判空

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;//空为true
}

9、打印 - 会将队列中的数据pop

//打印
void QueuePrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while(cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

三、队列的实际应用场景

1、保持公平性

实际上抽号机的底层原理就是用队列实现的，

(此处以小程序点餐所得到的取餐号为例子来分析)

程序会与抽号机相连接，用户得到的号码是该取号机队头上的数据；可能你会有疑问，小程序倘若是多线程的，如果有那么一瞬间多个用户同时下单(多个用户同时抽号，即有多个抽号机在使用同一程序)，那么这些用户会抽到同一个号码吗？

有多线程的概念一定就有同时取号的概念，如果该程序没有加锁，这些用户同时下单(极限思想，存在这样的可能性)，他们就会得到相同额号码；

为了避免这样情况的出现，就会为多线程的程序加上一个锁：当你要访问该队列(抽号的号码),首先是需要获得锁的，只有获得锁的人才能得到队列队头中的数据(号码)，而当其他人(其他线程)想取得队列对头中的数据的时候，倘若此锁已经别被人(另外的线程)占用了，那么该线程就会被阻塞在队列外；当等到前面线程将队头的数据获得之后，将锁归还；后面等待的线程才可以一一去获得号码(排队获取锁)

注：此处所讲的本质就是生产者、消费者模型(操作系统中地知识)；

• 生产者：抽号的人   
• 消费者：从中取号(eg. 取号窗口)；

2、广度优先遍历

注：在二叉树中会使用到广度优先遍历

• 广度优先遍历即以一个点为起点，一层一层一圈一圈，以广度的方式向外扩散来查找(有点像水纹的感觉)；

广度优先遍历可以做什么？

我们将好友关系用”图“来表示，当两人是好友的时候，他们之间便会有连线叫做"边"；

下图会涉及环的问题，即要以标记的方式(标记过后的便不再访问，类似于排雷中的操作)去避免 死循环的出现；

例如QQ中的好友推荐功能，若要向小张推荐好友，最好是推荐小张好友的好友；

• 小张的直接好友(一度好友)是小张直接用"边"连接出去的，上图表示为小梅和小陈；
• 小张的间接好友：小张好友的好友即小字和小跳；

如何找到小张好友的好友？

• 利用队列进行广度优先遍历；

先将小张放入队列中；接下来就是找小张的好友：将小张出队列，让小张的好友入队列；找小张好友的好友：让小梅出队列(假设小张的好友中小梅先入的队列)，再让小梅的好友入队列；小城出队列，再让小陈的好友入队列；

当小张的好友均出队列时，此时队列中的便是小张好友的好友；

注：上述过程利用了队列的先进先出；(小张出队列，让其好友入队列；小张的好友出队列，会让小张的好友的好友入队列)

如何判断小张的好友全部出队列了？

• 将小张的好友入队列的时候，小张肯定知道自己的好友有多少个；便可利用好友的个数写循环来控制出队列的次数；当小张的好友均出队列的时候，队列中剩下的便为小张好友的好友；

总结

队列：只允许在一端(队头)进行插入数据的操作，在另外一端(队尾)进行删除数据操作的特殊线性表，并且队列具有先进先出(FIFO)的特点；

队列最好不要用数组来实现，因为尾插或者头删存在一个一个挪动数据的可能性而导致效率低下；可以使用链表来实现，介于当可以用单链表实现的时候就采用单链表，能节约一点空间是一点空间，当单链表不能完成当前问题的时候再考虑使用双链表。队列可以用单链表实现，故而本文中的队列使用单链表来实现的；