上一篇最后我们分析了队列的利弊，故我们这里对队列进行优化。就有了这一篇，循环队列。 队列的问题主要便是入队的时间复杂度O(1).出队的时间复杂度0(n) 。还有就是当进行插入和删除操作后，线性表的开始空间可能会被空出来，会浪费且占用空间。
所以我们这里让队列首位相连变成了一个环，但是如何相连，相连之后入队和出队又是如何操作呢，相连以后会不会出现问题呢，出现问题又该如何解决呢，大家跟我一起往下看吧。
优化（循环队列）：
首先让队头指针和队尾指针一样随着数据元素的变化而变化。这样入队和出队的操作都是O(1)，然后我们将线性表首尾相连，当队头或队尾指针到达尾部时，如需后移可重新指向表头，变成一个环，指针从尾到头有一个周期性，也就是数线性表长度，指针+1对线性表长度取余就可以完成指针从头到尾的跳跃，这样就解决了空间浪费的问题。然后将一个空间预留出来不存任何元素，尾指针始终指向这个null空间，这时，队列满的条件是（rear+1）%n== front，队列为空的条件是 rear == front。这样可以解决判断队列满和队列空的条件都是（rear+1）%n==front的问题，这里n是线性表的长度，没法判断。如下图（这个图花了我很大的功夫，这篇博客的核心思想便在这俩张动图之中，大家一定要仔细看）：
图一：解决了空间浪费的问题
图二：解决判断队列满和队列空的条件都是（rear+1）%n==front的问题
用Java代码实现循环队列的顺序存储结构，使用ArrayQueueLoop实现Queue接口，重写Queue的方法，这里写的接口都是我们自己编写的，不是java里面自带的接口，大家注意一下，代码如下：
import java.util.Iterator;
//循环队列 底层用动态数组实现
public class ArrayQueueLoop implements Queue {
private E[] data; //定义数组
private int front; //头指针
private int rear; //尾指针
private int size; //有效元素个数
public ArrayQueueLoop(){
data= (E[]) (new Object[11]);//因为有一个空的空间，有效能存储的空间有10个
front=0; //初始化
rear=0;
size=0;
}
@Override
public int getSize() {
return size; //获取有效元素个数，直接返回size
}
@Override
public boolean isEmpty() {
return size==0&&front==rear; //循环队列为空的条件
|