队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示:
思路分析
insert操作：
1)将尾指针往后移：rear+1 ,当front == rear 【空】
2)若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear ==maxSize - 1[队列满]
代码演示：
class ArrayQueue {
private int maxsize;//数组最大容量
private int front;//队列头，指向队首元素，初始值-1
private int rear;//队列尾，指向队尾元素，初始值-1
private int[] arr;//存放数据的数组，模拟队列
//初始化队列
public ArrayQueue(int maxsize) {
this.maxsize = maxsize;
this.front = -1;
this.rear = -1;
this.arr = new int[maxsize];
}
//判断队列是否满？
public boolean isFull() {
return rear == maxsize - 1;
}
//判断队列是否空？
public boolean isEmpty() {
return rear == front;
}
//入队
public void insert(int n) {
if (isFull()) {
System.out.println("队列已满！操作失败！");
return;
}
rear++;
arr[rear] = n; //队尾上移，然后在新位置加入数据
}
//出队
public int remove() {
if (isEmpty()) {
throw new RuntimeException("队列为空！操作失败！");
}
front++;
return arr[front];
}
//读队首
public int getHead() {
if (isEmpty()) {
throw new RuntimeException("队列为空！操作失败！");
}
return arr[front];
}
//遍历
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空！");
return;
}
for (int e : arr) {
System.out.print(e + "\t");
}
}
}结果演示：
@Test
public void testArrayQueue(){
ArrayQueue queue=new ArrayQueue(5);
queue.showQueue();
queue.insert(1);
queue.insert(2);
queue.insert(3);
queue.insert(4);
queue.insert(5);
queue.showQueue();
queue.insert(6);//尝试插入6个数据，最后一个插入失败
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());//把所有数据移除完
queue.insert(1);//再加数据加不进去了
}
队列为空！
1 2 3 4 5 队列已满！操作失败！
1
2
3
4
5
队列已满！操作失败！上面这个demo其实是不完整的，数组中的位置不能复用，引入循环队列可以解决这个问题！
数组模拟环形队列
对前面的数组模拟队列的优化，充分利用数组。将数组看做是一个环形的。(通过取模的方式来实现)
思路如下:
1. front变量的含义做调整：front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素 。front 的初始值= 0
2. rear变量的含义做调整：rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定。rear 的初始值= 0
3.当队列满时的条件是(rear + 1) % maxSize == front
4.对队列为空的条件，rear == front
5.队列中有效的数据的个数(rear + maxSize - front) % maxSize
代码演示：
class CircleArrayQueue {
private int maxsize;//数组最大容量，等于实际容量+1，因为要在队尾预留一位
private int front;//队列头，指向队首元素，初始值0
private int rear;//队列尾，指向队尾元素后面的一位，初始值0
private int[] arr;//存放数据的数组，模拟队列
//初始化队列
public CircleArrayQueue(int maxsize) {
this.maxsize = maxsize;
this.front = 0;
this.rear = 0;
this.arr = new int[maxsize];
}
//判断队列是否满？
public boolean isFull() {
return (rear+1) % maxsize-front == 0;
//假设 maxsize=6，front=0，rear=5,则数组index的0-4位存满了数据，
}
//判断队列是否空？
public boolean isEmpty() {
return rear == front;
}
//入队
public void insert(int n) {
if (isFull()) {
System.out.println("队列已满！操作失败！");
return;
}
//直接赋值，因为rear对应的是当前队尾的后一位
arr[rear]=n;
//重新计算rear，可以从数组后面跑到前面
rear=(rear+1)%maxsize;
}
//出队
public int remove() {
if (isEmpty()) {
throw new RuntimeException("队列为空！操作失败！");
}
//先把队首数据保存
int temp=arr[front];
//重新计算front的位置
front=(front+1)%maxsize;
return temp;
}
//读队首
public int getHead() {
if (isEmpty()) {
throw new RuntimeException("队列为空！操作失败！");
}
return arr[front];
}
//遍历
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空！");
return;
}
for (int i=front;i<front+length();i++) {
System.out.print(arr[i%maxsize] + "\t");
}
System.out.println();
}
//队列长度
public int length(){
return (rear-front+maxsize)%maxsize;
//假设maxsize=6，即最大存5个数。front=5，rear=3,则数组index为0，1，2，5的位置应该有4个有效数据
}
}结果演示：
@Test
public void testCircleQueue(){
CircleArrayQueue queue=new CircleArrayQueue(6);
queue.showQueue();
queue.insert(1);
queue.insert(2);
queue.insert(3);
queue.insert(4);
queue.insert(5);
queue.insert(6);//尝试插入6个数据，最后一个插入失败，length=5
queue.showQueue();
queue.remove();
queue.remove();
queue.remove();//移除前三个数据
queue.showQueue();
queue.insert(6);
queue.insert(7);
queue.insert(8);
queue.showQueue();
queue.insert(9);//再次尝试插入4个数据，最后一个插入失败,length=2+3=5
}
队列为空！
队列已满！操作失败！
1 2 3 4 5
4 5
4 5 6 7 8
队列已满！操作失败！