数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 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
结果演示：
@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
队列已满！操作失败！
