【数据结构】队列的实现

0. 前言

上期博客给大家讲解了 栈以及栈的实现，今天再给大家讲一个特殊的顺序表结构，那就是队列！

下面就进入正题！一起学习一下吧！

1. 队列

1.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，

队列具有先进先出FIFO (First In First Out)

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

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

其实队列，换一种说法就相当于我们生活中的排队问题，不管干什么一般总是遵守先来后到的，
就是先来的（对头）先获取到资源，后来的不准插队，只能在最后面（队尾）排队等待。

1.2 队列的结构

它的结构如图所示：

2. 队列的实现

和栈的实现类似的想法，我们实现队列，既可以用数组实现，也可以用链表的结构实现。

如下图所示：

但是我们需要考虑的是，之前学习的哪一种结构可以更高效的实现我们的队列呢？

其实我们对比顺序表和链表的优缺点，

链表：空间的利用率高，不用扩容，头插头删高效

顺序表：空间利用率低，需要扩容，但是尾插尾删效率高

针对队列的结构，我们发现

因为如果使用数组的结构，出队列在数组头上出数据，也就是对顺序表进行删除的操作时，

需要挪动数据。效率是比较低的。

所以我们会选择使用链表来进行队列的实现。

2.1 准备工作

还是像往常一样，我们将队列其拆分为不同的文件进行设计

1️⃣：Queue.h 文件，用于函数声明
2️⃣：Queue.c 文件，用于函数的定义

3️⃣：Test.c 文件，用于测试函数

2.2 队列结构体的定义

队列的结构体定义跟链表结构体定义类似：

//队列节点 
typedef struct QueueNode
{struct QueueNode* next;//下一个节点的地址QDataType val;//节点存的数据
}QNode;

除了节点定义之外，我们可以再定义一个队列的结构体类型，

队列的结构体由三个部分组成：

phead是一个指向QNode结构体的指针，用于指向队列的队头元素。
ptail也是一个指向QNode结构体的指针，用于指向队列的队尾元素。
size表示队列中当前元素的个数。

typedef struct Queue
{QNode* phead;//队头指针QNode* ptail;//队尾指针int size;//队列中的元素个数
}Queue;

有细心的同学会很好奇，

为什么我们还需要定义一个Queue这样的结构体类型呢？

队头和队尾定义在刚才定义在QueueNode这个队列节点结构体类型不好吗？

也许是这样的结构体设计

//队列节点 
typedef struct QueueNode
{struct QueueNode* next;//下一个节点的地址QDataType val;//节点存的数据
}QNode, *phead, *ptail;
//对struct QueueNode 重命名为QNode，//根据队列节点类型，定义的队头指针phead和队尾指针ptail

能想到这样问题的同学，很优秀！👍👍👍

其实我们在定义链式队列结构体，也不是非得必须有如上这两个结构体的,

只不过有上面这两个结构体只是在调用函数时方便参数传递

我们在实现链表中也遇到过，对于链表的操作，插入删除操作时，指向链表的头指针可能会发生改变，我们在函数调用时，参数需要用二级指针接收。

这里也是同样的，在队列中插入元素，或者删除时，我们的队头指针phead和队尾指针rear会发生改变。我们在函数调用时，参数同样需要用二级指针接收。同学们会很容易犯同样的错误~

但如果再构造一个队列结构体Queue 我们的队头指针和队尾指针就是我们的结构体成员，

无论Queue这个类型有多少指向结点的指针，直接传递一个指向链队结点的类型的指针就可以了，

这样Queue这个类型这些指向结点的指针一并就传入了，如果想使用，我们可以通过结构体指针访问操作符，也就是这个箭头“->”访问，你看这样是不是就很方便了？

typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

这是我们在实现链式队列的一个小优化方式，同学们是不是get到了？是不是很妙呀？

2.3 队列初始化

初始化就是将记录的头指针和尾指针置空，元素个数置暂时赋为0

代码如下：

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

2.4 队尾插入

进行入队操作的时候，我们首先需要判断一下队列是否为空，

如果队列为空的话，需要将头指针和尾指针一同指向第一个结点，

当如果队列不为空的时候，入队列时，我们可以创建一个新节点，并放在记录好的尾节点的位置之后，成为新的尾节点，最后元素个数增加。

代码如下：

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//创建新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;//队列为空if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}//队列不为空else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;//插入数据之后不要忘了把元素个数+1
}

2.5 队头删除

我们分以下情况讨论，

在队列不为空的情况下，进行一个判断，如图所示，如果队列只有一个元素了（即头尾指针均指向了同一个结点），直接将头尾两指针制空（NULL）并释放这一个结点即可。

当队列含有2个以上元素时，我们需要将队列的头指针指向头指针当前指向的下一个元素并释放掉当前元素即可。最后元素个数减少。如图所示

代码如下：

void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);// 一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else // 至少2个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

2.6 返回队头元素

返回我们记录的头节点的值即可。

代码如下：

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

2.7 返回队尾元素

返回我们记录的尾节点的值即可。

代码如下：

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

2.8 队列元素个数

返回我们记录的元素个数即可。

代码如下：

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.9 队列判空

返回我们记录的元素个数是否为零。

代码如下：

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

2.10 队列销毁

类似于单链表的销毁，依次销毁每一个节点后将头尾置空，将元素个数置空。

代码如下：

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. 完整代码：

Queue.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}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 QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}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;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);/*QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL)pq->ptail = NULL;*/// 一个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else // 多个节点{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

test.c

#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);printf("%d ", QueueFront(&q));QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");return 0;
}