数组模拟队列进阶版本——环形队列（真正意义上的排队）

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

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

基本原理：

要知道我们实现队列的基本是头和尾。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
 */

• 数组模拟环形队列（真正意义上的排队）
•             昨天我们做了数组模拟队列的基本情景。可以进行排队和取出数据（最早的人离开队列)，但是我们发现，取出的地方不能重复利用。让我们的队列成为了一次性队列。今天我们来看如何将我们的队列改进称数组模拟环形队列。实现已释放位置的重复利用
•     基本原理：
•     分析说明：
•         1：尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满]
•         2：rear == front [空]

__EOF__