1、普通队列存在什么问题？
队列大家都知道，有几个重要的属性：
rear：指向队列的尾巴，即最后一个元素所在的位置，初始值为-1
front：指向队列的头部的前一个位置，初始值也为-1
-
capacity：队列的容量
立即学习“Java免费学习笔记（深入）”；
空队列的rear和front都等于-1，入队时，front不动，rear++，当 rear == capacity - 1时，队列已满；出队时，rear不动，front++，当front == rear时，队列为空。看起来很完美，但实际上有问题。假如一个队列capacity = 3，入队了三个元素，此时front = -1; rear = 2，然后再将三个元素都出队，此时front = 2, rear = 2。这时队列明明是空的，但是却不能再入队元素的，因为满足rear = capacity - 1，也就是相当于这队列是一次性的，用过之后就不能再用了，即使为空也不能再入队了，造成空间的浪费，所以环形队列就出现了。
2、环形队列实现思路：
环形队列中的几个重要属性：
rear：指向队列尾巴的后一个位置，初始值为0
front：指向队列的头部，即第一个元素所在的位置，初始值为0
-
capacity：队列的容量
立即学习“Java免费学习笔记（深入）”；
下面是环形队列的一些算法：
队列为空时：
front == rear队列已满时：
(rear + 1) % capacity == front获取队列元素个数：
(rear + capacity - front) % capacity入队操作时：
rear = (rear + 1) % capacity出队操作时：
front = (front + 1) % capacity;
判断队列是否已满是环形队列中最重要也是最难理解的地方。假如有一个队列capacity = 3，入队操作如下：
第一个元素入队：
front = 0，因为(rear + 1) % capacity = 1 % 3 != front，所以元素可以入队，元素入队后rear = 1；第二个元素入队：
front = 0，因为(rear + 1) % capacity = 2 % 3 != front，所以元素可以入队，元素入队后rear = 2；第三个元素入队：
front = 0，因为(rear + 1) % capacity = 3 % 3 == front，所以元素不能入队，队列已满；
队列容量明明是3，只入队了两个元素就告诉我队列满了？没错，这种判断队列是否已满的算法需要牺牲数组的一个空间。
现在进行出队操作：
第一个元素出队：
front = 1，rear = 2，(rear + 1) % capacity = 3 % 3 = 0 != front。
可以发现，当一个元素出队后，又满足入队条件了，所以数组空间就可以重复利用了。
3、代码实操：
public class CircleQueue{
private int capacity;
private int front;
private int rear;
private Object[] arr;
public CircleQueue(int capacity){
this.capacity = capacity;
this.arr = new Object[capacity];
this.front = 0;
this.rear = 0;
}
public boolean isFull(){
return (rear + 1) % capacity == front;
}
public boolean isEmpty(){
return rear == front;
}
public void addQueue(E e){
if (isFull()){
throw new RuntimeException("队列已满，入队失败");
}
arr[rear] = e;
// rear指针后移
rear = (rear + 1) % capacity;
}
public E getQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，出队失败");
}
E val = (E) arr[front];
front = (front + 1) % capacity;
return val;
}
public int getSize(){
return (rear + capacity - front) % capacity;
}
// 遍历
public void showQueue(){
if (isEmpty()){
return;
}
for (int i = front; i < front + getSize(); i++) {
System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);
}
}
public static void main(String[] args){
CircleQueuequeue = new CircleQueue<>(3);
queue.addQueue(1);
queue.addQueue(2);
queue.showQueue();
//queue.addQueue(3);
System.out.println(queue.getSize());
System.out.println(queue.getQueue());;
queue.addQueue(3);
queue.showQueue();
}
}
