概念
队列
先进先出，后进后出：比如生活中的排队买票，先来的先买，后来的排队，最后一个最后一个买。
队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
——维基百科
循环队列
假如队列是一个固定长度的队列，而进来的元素都只能往队列的后面排，最终会排到队列的最后一个位置。而前面如果有元素已经出来空出了位置，但此时也没法让其他元素进来，出现了伪溢出的现象（虽然队列已经排到尾了，但前面还有空位），而循环队列就解决了这个问题。
当队列排到尾，而前面还有空位的话，那就从头开始进入。但队列依旧遵循先进先出的原则，性质并没有被改变。
属性
循环队列需要以下的几个属性：
int maxSize：记录队列的最大容量
T[] arr：由于是固定长度，所以用数组来存储元素，而长度就根据maxSize来初始化
int front：记录队列中头元素的坐标
int rear：记录队列中末尾元素的后一位坐标（比如当前最后一个元素的坐标为2，则rear = 3）
编写时的两个问题：
1. 队列空/队列满
判断队空：当front == rear 为空
判断队满：当 front == (rear+1) % maxSize 为满
正常情况下，当队列满时，front 和 rear 应该指向的是同一个坐标，但是这样就会与队空情况的坐标位置一样，后续作判断时有分歧。所以这里为了方便后续判断队列空满，这里假设还剩一个位置时，队列就满了，不再允许入队， 此时 rear 应该在 front 的前一位。
所以当 rear+1 == front 为满，但由于是循环队列，如上图，rear 的坐标为 7，7+1!=0，为此通过%取余使 (7+1)%8 == 0，同时也不影响其他坐标情况的判断，如 6+1 == (6+1)%8 （如下图）
队满状态
2. 有效元素个数
情况一：当 front<rear 时，size = rear - front;
情况二：当 front > rear 时，size = rear + (maxSize-front)
为了方便，通过（rear + maxSize - front) % maxSize 公式来获取元素个数；
这里可能有点转不过弯，首先要知道，当一个数%一个比他大的数取余，得到的结果跟原来的数是一样的。
所以对于第一种情况，rear - front 是不会大于maxSize的，那么情况一的公式加maxSize再摩尔maxSize 的结果还是会等于 rear - front
对于情况二： rear + (maxSize-front) 这个结果再摩尔maxSize 也不会被改变
实现代码
public class CircularQueue<E> {
private Integer maxSize;
private E[] arr;
private Integer front = 0;
private Integer rear = 0;
/**
* 构建时初始化存储元素的数组
*
* @param maxSize 指定队列的最大容量
*/
public CircularQueue2(Integer maxSize) {
this.maxSize = maxSize;
this.arr = (E[]) new Object[maxSize];
}
/**
* @return 返回当前队列是否为空
*/
public boolean isEmpty() {
//这里规定当 front 等于 rear 时，队列为空
if (this.front == this.rear) {
return true;
}
return false;
}
/**
* 入队
*
* @param element
*/
public void enqueue(E element) {
//判断队列是否为满(当rear+1等于front时为满)
if ((this.rear + 1) % this.maxSize == this.front) {
throw new RuntimeException("queue is full");
} else {
//未满时直接入队
this.arr[this.rear] = element;
//rear的坐标往后移
this.rear = (this.rear + 1) % this.maxSize;
}
}
/**
* 出队
*
* @return 返回出队的元素
*/
public E dequeue() {
//判断队列是否为空
if (this.isEmpty()) {
//队列为空抛出异常
throw new RuntimeException("queue is empty");
} else {
//先读取队列的头元素
E element = this.arr[this.front];
//front坐标后移
this.front = (this.front + 1) % this.maxSize;
return element;
}
}
/**
*
* @return 获取队列的头元素
*/
public E getFront() {
return this.arr[this.front];
}
/**
*
* @return 获取队列的有效长度
*/
public int getSize() {
return (this.maxSize - this.front + this.rear) % this.maxSize;
}
}
