环形队列（环形队列为什么要空一个）

科技前沿 • 2025-06-02 20:09 • 阅读 46

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg>

讯享网

本篇笔记是我在B站上跟着尚硅谷教程进行学习，记录的学习笔记，在学习中产生了疑问，并通过查找资料解决了相关问题。

队列介绍

1）队列是一个有序列表，可以用数组或是链表表示。

2）遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。

front及rear分别记录队列前后端的下标，front随着数据的输出而改变，而rear则是随着数据输入而改变。

讯享网

代码实现

讯享网

问题分析并优化：

目前数组使用了一次就不能用了，没有达到复用的效果
我们要使用算法，将目前的数组改成一个环形的队列取模%

数组环形队列思路：

1、front变量的含义做一个调整：front就指向队列的第一个元素，就是是说arr[front]就是队列的第一个元素，front初始值为0；

2、rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，rear的初始值为0；

3、队列满的条件：(rear+1)%maxSize ==front

4、队列空的条件是：rear == front

5、此时队列的有效长度是： (rear+maxSize-front)%maxSize

遇到的问题（循环队列空一个元素的位置）

在得到队列满的条件：(rear+1)%maxSize ==front时，我充满了疑惑，怎么算都觉得在rear已经表示最后元素的后一位了，这种情况下加一肯定是不对的，后来我查了一些资料。
别人规定的循环队列

那么，循环队列为什么用空一个元素的位置呢？？？

这个是根据需要来用的
循环队列中，由于入队时尾指du针向前追赶头指针；zhi出队时头指针向前追赶尾指针，造成dao队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是“空”还是“满”。
解决这个问题的方法至少有三种：
①另设一布尔变量以区别队列的空和满；
②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（即队列长度）。