2025年环形队列（环形队列的基本运算）

编程日记 • 2025-01-26 22:33 • 阅读 49

一、队列的概念

二、队列的常见术语

（1）入队和出队

（2）对头和队尾

（3）空队

三、队列的定义

四、队列的相关方法

五、相关方法的实现

1、队列的初始化及销毁

2、队尾插入和队头删除

3、取队头和队尾的数据

4、统计队列的个数

5、判空

六、总结

队列是一种运算受限制的线性表，但是它与栈的不同在于队列时限制在表的两端进行操作的线性表，它遵循的是“先进先出”的原则。因此它的英文名是Queue，由于先进先出的原则，也被称为先进先出的线性表（FIFO，first in first out）。

队列中数据的插入操作叫做入队；相反，删除操作又叫做出队。

允许一段进行插入操作的一端称为队尾，允许删除操作的一端称为队头。

不含任何数据元素的队列称为空队。

队列实现需要队尾数据的插入和队头数据的删除，所以我们考虑使用链表，双链表毫无疑问是可以使用的，但是我们这里要优先考虑单链表能否实现（成本等原因）。因此我们先定义一个单链表：

并且接下来的队列相关操作的实现中，我们是要常常传递头指针和尾指针的，所以我们可以通过再定义一个结构体来简化以下参数的传递。这样不仅优化了参数的传递，并且不需要考虑在传递时二级指针的传递。

队列的相关方法通常有以下几种：

队列的初始化本质及单链表的初始化，我们需要首先将头节点和尾节点置为NULL，然后将size置为0。

队列的销毁同样是对链表的销毁，需要我们循环释放掉开辟的每一个空间并置空，避免出现野指针。

前边我们提到，队列的插入是在链表的尾，而删除则是在链表的头。

在插入时，我们首先要开辟一个空间，用来存放要插入的数据，接着判断是否为空队列，如果为空队列，我们需要将头节点和尾节点指向新开辟的新节点；如果不是，我们只需将队尾节点指向新开辟的新节点，然后让size加一即可。

在删除操作中，我们要先判断是否为空队列，接着再来判断是否为最后一个数据，如果是最后一个数据，我们只要将其释放，并置为空即可。如果是多个节点的删除，需要将头节点的下一个节点保存，方便在释放掉头节点之后将新的头节点设置为下一个节点即可。最后将size进行减一操作。

取队头及对队尾数据我们首先要想到有返回值，并且返回值类型为自定义数据类型。接着在实现函数中，我们只需要判断传递的结构体指针和头节点、尾节点是否为空即可，然后直接返回val值。

之前我们在定义Queue结构体时，我们不仅包含了头节点和尾节点，还包含了size，它表示的就是队列的个数，我们只需要在插入和删除时进行加一减一操作即可，因此在统计方法实现中只需要返回size即可。

队列的判空即判断队列个数是否为0即可。

队列的定义及相关方法的实现中，我们需要注意一二级指针的传递，但是如果我们定义一个结构体，包含头尾节点，我们就可以只传递结构体指针即可。并且我们在结构体中加入size，就可以在相关方法（统计个数、判空）的实现中实现简化。

队列的相关知识中还包含循环队列，我们下章在讲。