队列是一种带限制的线性表，与普通线性表相比，是一种插入和删除位置受限的线性表。队列限制只能在线性表的头部删除，只能在线性表的尾部插入，因此队列遵循先入先出的原则。可以解决程序设计中的类排队问题。
文尾附代码地址。
准备阶段
- 需要两个变量
front及rear分别记录队列前后端的下标，其中front队头，会随着数据出队而改变；rear队尾，随着数据入队而改变 - 使用数组模拟队列，设数组大小的maxSize，那么当rear=maxSize-1时再入队会发生溢出，其中
front=0 并且 rear=maxSize-1时再入队认为是真溢出；front不等于0 并且 rear=maxSize-1时再入队认为是假溢出。
为了解决假溢出的问题，可以通过
取模%的方式实现循环队列。将队列想象成一个循环的表，分配给队列的存储空间可以循环使用，当rear为maxSize-1时，而front不为零（即队列的开始端空着），可以从头使用空着的空间，即base[maxSize-1]的下一个元素是base[0]。front同理。
- 为什么有少用一个元素空间的约定？
一般认为空队列的条件是front=rear=0，当从队尾插入一个元素时，front=0，rear=1，你可以想象一个列表，此时列表中只有一个元素，这个元素即是队头，又是队尾。此时队头front仍指向队列的第一个元素，即front=0；但队尾rear实际指向的是队尾元素的下一个元素的下标，即rear=1。
这样的话，当队列满时，此时下标为maxSize-1的元素刚入队，根据上述循环使用数组存储空间的构想，rear需要指向的是下标为0的元素，即rear=0。如果之前没有出队，此时front=0，队列已满（实际上rear=maxSize，此时
rear % maxSize=front）。但是这个队满的条件包含队空的条件front=rear=0，无法区分队空和队满。
所以为了解决队空和队满判断条件相同的问题，就约定少使用一个元素空间，即manSize大小的数组，最多能存储maxSize-1个队列元素。约定的不使用的那个元素是数组的最后一个元素，判断队满的条件也就变成了
(rear+1)%maxSize=front。
需要注意的是，少使用一个元素空间是一个约定俗成解决方案，并不是唯一方案，可以另设一个标志区分队空，队满；还可以另设一个变量记录元素个数。
使用数组模拟循环队列
class CircleQueue {
private int front;
private int rear;
private int[] arr;
private int maxSize;
public CircleQueue(int size) {
//front rear初始值都为0，rear这里指向的是最后一个元素的后一个元素
maxSize = size;
arr = new int[maxSize];
}
}
- 判断队空
public boolean isEmpty() {
return front == rear;
}
- 判断队满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
- 入队
public void addQueue(int num) {
if (isFull()) {
System.out.println("队列已满，无法入队");
return;
}
arr[rear] = num;
rear = (rear + 1) % maxSize;
}
- 出队
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无法出队");
}
int val = arr[front];
front = (front + 1) % maxSize;
return val;
}
- 显示队头元素
public int peekQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front];
}
- 遍历队列元素
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空，没有数据");
}
//从front遍历到rear
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]); //格式化输出
}
}
//获取当前队列有效数据的个数
public int size() {
return (rear + maxSize - front) % maxSize;
}
