环形队列的优缺点（环形队列特点）

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

 <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>

讯享网

其实在内存上并没有所谓的环形队列，环形队列只是基于数组线性空间来实现。

环形队列优点：

避免假溢出现象。（因为在数组里，头尾指针只增加不减少，被删元素的空间再也不能被重新利用。会造成尾指针已经到达了队列的最后一位，而头指针前面没有满的情况。）
广泛用于网络数据的收发。和不同程序之间的数据交换。
首尾相连的FIFO数据结构，采用数据的线性空间，能快速的知道队列是否满或者空。

首先声明属性，其中rear属性需要重点关注，非常重要，它指向队尾元素的后一位，预留了一个数据空间作为一个约定。：

讯享网

创建构造器：

几个比较重要的方法：

在这里插入图片描述
讯享网

头指针=尾指针说明队列为空。

讯享网

判断环形队列是否满之前需要知道，在环形队列中front头指针能不能和普通队列中的头指针一样，伴随数据的写入而一直进行着自增？答案是不行。设计环形队列的初衷便是可以重复利用已经删除数据的空间，避免假溢现象的出现。
而且在判断一个环形队列是否满时，只需要关心尾指针以及头指针的关系即可。头指针必定会跟随着数据的写入而进行着自增，这样在队列满时就会出现和队列为空时一样的情况。都为front = rear，即头指针 = 尾指针，那么我们无法分辨究竟是队列满还是对列空，存在一定的歧义。
所以我们需要用一种新的方式来判断队列是否为满，同时与队列是否为空做出区别。

本文采用取模运算：
在这里插入图片描述

柱状图也许不方便理解环形队列已经满的情况。

通过下图可以看到在队列已经满的情况下rear指向了最后一个元素，但其实还有一个空的位置，这个时候需要将rear+1，空出来的位置是作为一个约定存在，是动态变化的。而在环形队列中数据一直写入会造成尾指针rear一直自增造成数组越界。所以需要加下标控制在一个范围以内，而在本文中，这个范围就是头指针front至最大容量maxSize的范围。而取模操作恰好能满足这个需求点。

例如：

在front = 0，rear = 3，maxSize = 7的情况下，（rear + 1） % maxSize = 0.6，而0.6 != 0，所以数组没有满，依然可以存储数据。
在front = 0，rear = 6，maxSize = 7的情况下，（rear + 1） % maxSize =0，而0 = 0，数组已经存满。

在这里插入图片描述

取模的意义在于将arr下标控制在front和maxSize之间，如果不取模，rear会一直加1，超出队列容量。

添加数据时先判断是否已满。
因为rear就是代表元素的位置，所以直接将要添加的数据放在尾指针rear处即可。
但是数据存放完毕后要将rear向后移动一位，根据前文说到的数组越界问题依旧存在，所以也要进行取模运算。

讯享网

在从环形队列获取数据的时候要先判断队列是否为空。
获取数据时直接获取头指针front所在位置的数据即可。
剩下的逻辑与添加数据的逻辑一样，也得在取模后把指针往后移动一位。
不一样的一点在于取值的时候需要吧值保存在一个临时变量里面。

打印环形队列有两点需要注意：

1、不能直接i< arr.length，现在是环形队列，是一直循环存储的。

环形队列有两种情况：

front < rear (队列没满) —> maxSize - front = 有效数据个数。
front > rear (队列已经存满) —> 0 + rear
两个式子合起来为：( maxSize - front ) + ( 0 + rear )
即maxSize - front + rear
front的作用是提供一个起始位置。而取模是为了使下标数字一直在front和maxSize的范围以内。

2、打印的时候不能使用i = 0，要使用数据坐标作为遍历起始值。

讯享网

直接根据下标获取即可。

讯享网

环形队列的优缺点（环形队列特点）

1、不能直接i&lt; arr.length，现在是环形队列，是一直循环存储的。

2、打印的时候不能使用i = 0，要使用数据坐标作为遍历起始值。

相关推荐

1、不能直接i< arr.length，现在是环形队列，是一直循环存储的。