1.1 什么是循环队列
循环队列：具有队头指针（front）和队尾指针（rear），指示队列元素所在的位置，避免删除元素时移动大量元素。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作，先进先出（First In First Out，FIFO）。
循环队列特性：
- 只能队尾插入元素、在队头删除元素。
- 先进先出（First In First Out）的线性表，先进入的元素出队，后进入的元素才能出队。
优点：
- 相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
- 适合处理用户排队等待的情况。
时间复杂度:
- 读取时的时间复杂度为O(1)。
- 插入、删除时的时间复杂度为O(1)。
1.2 图解循环队列
1、 顺序队列：
队列的顺序存储形式，可以用一个一维数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。
顺序存储方式：
2、 队列的入队和出队情况：；
假设现在顺序队列Q分配了6个空间，然后进行入队出队操作，过程如图所示：
2.1 开始时为空队，front=rear，如图所示：
2.2 元素a1进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：
2.3 元素a3，a4，a5分别按顺序进队，尾指针rear依次后移，如图所示：
2.4 元素a1出队，头指针front（整型下标）后移一位，如图所示：
2.5 元素a2出队，头指针front（整型下标）后移一位，如图所示：
2.6 元素a6进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：
元素a7进队，此时尾指针rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为"假溢出"。
2.7 上面第【2.6】步元素a6进队之后，尾指针rear要后移一个位置，此时已经超过了数组的下标，即rear + 1 = maxSize（最大空间数6），那么如果前面有空闲，rear可以转向前面0的位置，如图所示：
2.8 然后元素a7进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：
2.9 元素a8进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：
2.10 队满临界条件判断，如图所示：
这时候虽然队列空间存满了，但是出现了一个大问题，队满时front = rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针rear的下一个位置front是时，就认为是队满。如图所示：
上述到达尾部又向前存储的队列称为循环队列，为了避免"假溢出"，我们通常采用循环队列。
循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：rear = ( rear + 1) % maxSize。
2.10 为什么要对maxSize取余
主要是为了处理临界状态，即rear向后移动一个位置rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：
上图中最大空间maxSize，当rear=maxSize-1时，(rear + 1) % maxSize = 0，而且 front =0 ，正好满足队满的条件：(rear+1) % maxSize = front，此时为队满。
因此无论是front还是rear向后移动一个位置时，都要加1与最大空间maxSize取模运算，处理临界问题。
1、 总结；
如下表格中，记录循环队列状态和说明：
| 状态 | 说明 |
|---|---|
| 队空 | front=rear; // rear和front指向同一个位置 |
| 队满 | (rear + 1) % maxSize = front; // rear向后移一位正好是front |
| 入队 | [rear] = x; // 将元素放入rear所指空间，rear =(rear+1) % maxSize; //rear向后移一位 |
| 出队 | element = data[front]; //用变量记录data[front]所指元素，front = (front + 1) % maxSize // front向后移一位 |
1、 循环队列中存了元素个数；
因为队列是循环的，所以存在两种情况：
4.1 rear>= front，这种情况队列中元素个数为：rear - front=4-1=3。如下图所示：
4.2 rear< front，如下图所示：
此时，rear=4，front = maxSize-2，rear-front = 6-maxSize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值+maxSize计算元素个数，即：rear - front + maxSize = 6 - maxSize + maxSize = 6，元素个数为6。
4.3 那么在计算元素个数时，可以分两种情况判断：
- rear>= front：元素个数为rear-front；
- rear<front：元素个数为rear-front+ maxSize；
- 4.4 采用取模的方法把两种情况统一为一个语句：
队列中元素个数：(rear - front + maxSize)% maxSize
当rear-front为负数时，加上maxSize再取余正好是元素个数，如(-2+6)%6=4；当rear-front为正数时，加上maxSize超过了最大空间数，取余后正好是元素个数，如(3+6)%6=3。
1.3 Java实现循环队列
CustomCyclicArrayQueue类是一个自定义实现了循环队列。
package com.yuanxw.datastructure.chapter1;
import java.util.NoSuchElementException;
/**
* 自定义实现循环队列
*/
public class CustomCyclicArrayQueue {
public static void main(String[] args) {
CyclicArrayQueue arrayQueue = new CyclicArrayQueue<>(3);
System.out.println("获得arrayQueue元素列表：" + arrayQueue);
System.out.println("arrayQueue.add()，添加【Java】元素，执行返回结果：" + arrayQueue.add("Java"));
System.out.println("arrayQueue.add()添加【C】元素，执行返回结果：" + arrayQueue.add("C"));
System.out.println("arrayQueue.add()添加【Python】元素，执行返回结果：" + arrayQueue.add("Python"));
/**
* 添加第4个元素时：arrayQueue.add("C++");
执行结果：
Exception in thread "main" java.lang.IllegalStateException: Queue full
at com.yuanxw.datastructure.chapter1.CustomArrayQueue$ArrayQueue.add(CustomArrayQueue.java:88)
at com.yuanxw.datastructure.chapter1.CustomArrayQueue.main(CustomArrayQueue.java:17)
*/
System.out.println(arrayQueue);
System.out.println("获得arrayQueue队列个数："+arrayQueue.size());
System.out.println("获得arrayQueue队列中的第一个元素："+arrayQueue.peek());
System.out.println("获得arrayQueue队列中的第一个元素："+arrayQueue.peek());
System.out.println(arrayQueue);
System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
System.out.println(arrayQueue);
System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
System.out.println(arrayQueue);
System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
System.out.println(arrayQueue);
/**
* 当队列中的元素为空时，调用 arrayQueue.take()方法，抛出异常。
* Exception in thread "main" java.util.NoSuchElementException
* at com.yuanxw.datastructure.chapter1.CustomCyclicArrayQueue$CyclicArrayQueue.take(CustomCyclicArrayQueue.java:146)
* at com.yuanxw.datastructure.chapter1.CustomCyclicArrayQueue.main(CustomCyclicArrayQueue.java:36)
*/
// System.out.println("当前arrayQueue对象中take()数据值为：" + arrayQueue.take());
System.out.println("arrayQueue.add()，添加【C++】元素，执行返回结果：" + arrayQueue.add("C++"));
System.out.println("arrayQueue.add()添加【JavaScript】元素，执行返回结果：" + arrayQueue.add("JavaScript"));
System.out.println("arrayQueue.add()添加【C#】元素，执行返回结果：" + arrayQueue.add("C#"));
System.out.println(arrayQueue);
}
static class CyclicArrayQueue<E> {
// 队列头部，指向队列头的第一个位置。默认值为：0
private int front;
// 队列尾，指向队列尾的位置。默认值为：0
private int rear;
// 数据
private E[] data;
// 容量
private int maxSize;
/**
* 构造函数
* @param capacity
*/
public CyclicArrayQueue(int capacity) {
this.front = 0;
this.rear = 0;
// 预留一个判断是否队满。
this.maxSize = capacity + 1;
this.data = (E[])new Object[maxSize];
}
/**
* 判断是否已经满
* @return
*/
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty(){
return rear == front;
}
/**
* 获取大小
* @return
*/
public int size(){
return (rear - front + maxSize) % maxSize;
}
/**
* 添加元素
* @param element
* @return
*/
public boolean add(E element){
if(element == null){
throw new NullPointerException("can not add element be null");
}
// 队列已经满
if(isFull()){
throw new IllegalStateException("Queue full");
}
data[rear] = element;
rear = (rear + 1) % maxSize;
return true;
}
/**
* 返回队列中的第一个元素
* @return
*/
public E get(){
if(isEmpty()){
throw new NoSuchElementException();
}
E element = data[front];
front = (front + 1) % maxSize ;
return element;
}
/**
* 返回队列中的第一个元素
* @return
*/
public E peek(){
if(isEmpty()){
throw new NoSuchElementException();
}
return data[front];
}
/**
* 删除此队列的头并返回
* @return
*/
public E take(){
if(isEmpty()){
throw new NoSuchElementException();
}
E takeValue = data[front];
front = (front + 1) % maxSize ;
return takeValue;
}
@Override
public String toString() {
StringBuffer buffer = new StringBuffer();
if(isEmpty()){
return buffer.append("[]").toString();
}
buffer.append("[");
for (int i = front; i < front + size(); i++) {
buffer.append(data[i%maxSize]).append(",");
}
// 删除最后一个逗号
buffer.deleteCharAt(buffer.length()-1);
buffer.append("]");
return buffer.toString();
}
}
}
执行结果：
获得arrayQueue元素列表：[]
arrayQueue.add()，添加【Java】元素，执行返回结果：true
arrayQueue.add()添加【C】元素，执行返回结果：true
arrayQueue.add()添加【Python】元素，执行返回结果：true
[Java,C,Python]
获得arrayQueue队列个数：3
获得arrayQueue队列中的第一个元素：Java
获得arrayQueue队列中的第一个元素：Java
[Java,C,Python]
当前arrayQueue对象中take()数据值为：Java
[C,Python]
当前arrayQueue对象中take()数据值为：C
[Python]
当前arrayQueue对象中take()数据值为：Python
[]
arrayQueue.add()，添加【C++】元素，执行返回结果：true
arrayQueue.add()添加【JavaScript】元素，执行返回结果：true
arrayQueue.add()添加【C#】元素，执行返回结果：true
[C++,JavaScript,C#]
–