数组模拟环形队列（真正意义上的排队）昨天我们做了数组模拟队列的基本情景。可以进行排队和取出数据（最早的人离开队列)，但是我们发现，取出的地方不能重复利用。让我们的队
要知道我们实现队列的基本是头和尾。rear和front。这两个的指向决定了队列的头尾。也就是队列本身。这个具体指向头部本身索引或者前一个后一个不是固定的。是根据具体算法而定的。这次我们规定头和尾默认指向0索引。
对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式式来实现即可)
分析说明： 1：尾索引的下一个为头索引时表示队列满，即将队 列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 满] 2：rear == front [空]
代码如下：
package com.joseph.sparseArray;
import java.util.Map;
import java.util.Scanner;
public class CircularQueue {
public static void main(String[] args) {
CQueue cQueue = new CQueue(5);
Scanner sc = new Scanner(System.in);
int i;
while(true) {
System.out.println("---------------排队系统--------------");
System.out.println("---------------1：排队咨询--------------");
System.out.println("---------------2：结束排队(最早成功的人)--------------");
System.out.println("-------------- 3：查看当前排队详情--------------");
System.out.println("---------------88:SHOW REAR AND FRONT");
System.out.println("---------------4：退出--------------");
i = sc.nextInt();
switch (i) {
case 1:
System.out.println("请输入你的电话");
int tel = sc.nextInt();
cQueue.add(tel);
if(cQueue.rear == 0){
if(cQueue.arr[cQueue.MaxSize-1] == tel) {
System.out.println("排队成功！");
System.out.println("已结束最早完成排队的人。当前空闲位置为：" + ((cQueue.MaxSize - 1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
}
}else if (cQueue.arr[cQueue.rear - 1] == tel) {
System.out.println("排队成功！");
System.out.println("已结束最早完成排队的人。当前空闲位置为：" + ((cQueue.MaxSize -1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
break;
} else {
System.out.println("排队失败！");
System.out.println("已结束最早完成排队的人。当前空闲位置为：" + ((cQueue.MaxSize -1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
break;
}
case 2:
int oldFront = cQueue.front;
cQueue.get();
if (cQueue.front != oldFront) {
System.out.println("已结束最早完成排队的人。当前空闲位置为：" + ((cQueue.MaxSize -1) - (cQueue.rear - cQueue.front + cQueue.MaxSize) % cQueue.MaxSize));
break;
}
System.out.println("结束失败");
break;
case 3:
cQueue.List();
break;
case 4:
System.out.println("谢谢使用！");
break;
case 88:
System.out.println("front:" + cQueue.front);
System.out.println("rear:"+cQueue.rear);
}
}
}
}
class CQueue{
int MaxSize ;//数组最大容量，因为我们的REAR(尾部)指向的是最后一个数据索引的后一个。这也就是说我们的真实存储长度要比MaxSize小一个。因为总要空出一个由rear指向。这是一个约定。前面有说到。
int rear ;//尾部。指向队列最后一个数据的后一个位置
int front ;//头部。直接指向第一个数据索引下标
int arr[] ;//数组
public CQueue(int MaxSize){//基本没变。rear和front初始值和上次不一样。不懂得先看上次数组模拟队列基础版
this.MaxSize = MaxSize ;
arr = new int[MaxSize];
this.rear = 0;
this.front = 0;
}
public boolean isFull(){
return (rear+1)%MaxSize == front ;//由于环形队列，其实队列满的状态。是他们两个差"一个"，因为rear指向的是数据的后一个。而front指向的第一个数据。因为是环形，0和4要联系起来只差一个就需要取模。利用rear+1和MaxSize取模。等于front就代表满了。这个需要好好理解。比较有难度
}
public boolean isEmpty(){//判断为空。当他们两个相等。不管在什么位置。就代表没有数据。
return rear == front ;
}
public void add(int key){//添加数据
if(isFull()){
System.out.println("QUEUE IS FULL,CAN'T ADD ANYTHING");
return ;
}
arr[rear] = key ;//直接将rear的下标赋值。
rear = (rear+1)%MaxSize ;//这里不能再自增了。因为是环形的。需要利用+1后取模实现周期性。否则会下标越界
}
public int get(){
if(isEmpty()){
throw new RuntimeException("QUEUE IS EMPTY,NO THINGS BE GETED");
}
int temp = arr[front] ;//这里先把头部数据拿出来。放到temp
front = (front+1)%MaxSize ;//给front移位。当数据取出。就往后+1作为初始第一个数据。但是是环形的。继续利用+1后取模实现周期性+1.不然会下标越界
return temp ;
}
public void List(){
//判断
if(isEmpty()){
System.out.println("QUEUE IS EMPTY!");
return ;
}
for(int i = front ; i < (rear - front + MaxSize)%MaxSize +front ;i++){//这里不能用传统思维去输出了。要从front开始输出。也就是队列的开头
//而i的范围。不再是队列长度。而是队列的有效数据个数+front。前面有算出是（rear-front+MaxSize)%MaxSize,其实rear是最后一个数据的后一个，而front就是第一个。我认为rear-front就是有效数据个数。而由于环形。往往出现负数。所以继续取模达到绝对值的效果。由于我们是环形的。front初始位置会由于用户取出导致变化。所以必须再加上front。因为front才是开始的位置。再加上有效数据个数。就是i的范围
System.out.printf("队伍第[%d]号 ： %d\n",i%MaxSize,arr[i%MaxSize]);//这里输出用printf方法做一个格式化。不能用i，要取模。否则会越界
}
}
}
/**
* @author JosephWang
* @date 2021/8/10 11:58
*/