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



目录

一、队列的概念

二、队列的常见术语

    （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，就可以在相关方法（统计个数、判空）的实现中实现简化。

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

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/45658.html