数组模拟环形队列（真正意义上的排队）

昨天我们做了数组模拟队列的基本情景。可以进行排队和取出数据（最早的人离开队列)，但是我们发现，取出的地方不能重复利用。让我们的队列成为了一次性队列。今天我们来看如何将我们的队列改进称数组模拟环形队列。实现已释放位置的重复利用

基本原理：

要知道我们实现队列的基本是头和尾。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]号 ： %dn",i%MaxSize,arr[i%MaxSize]);//这里输出用printf方法做一个格式化。不能用i，要取模。否则会越界         }     } } /**  * @author JosephWang  * @date 2021/8/10 11:58  */ 

表情 点击这里取消回复。