数组实现环形队列

image.png
看我画的图！
我这里实现的是循环队列

---

front：指向第一个数据的位置
rear：指向最后一个数据的下一个位置
maxSize：数组的长度
重点：rear指向的地方永远为空，不存数据，我们这里牺牲了数组的一个单位来实现对队列为满条件的判断，你可以认为这个数组能存的最大数据个数永远为maxSize-1（数组长度减一）

---

front和rear的初始值都为0
判断队列为空：front==rear
判断队列为满：rear=(rear+1)%maxSize
计算队列元素个数：（rear-front+maxSize）%maxSize

---

它的简易版为单向队列，请点击传送门

---

以下为代码实现，演示请使用如下命令：
javac -encoding utf-8 CircleQueue.java
java CircleQueue

---

import java.util.Scanner;
public class CircleQueue{

    private int front;//指向第一个数据的位置
    private int rear;//指向最后一个数据的下一个位置
    private int maxSize;//数组大小
    private int[] arr;
    public static void main(String[] args) {
        
        CircleQueue cq = new CircleQueue(4);
        char key=' ';//接收用户输入的第一个字符
        Scanner scanner =new Scanner(System.in);//读取用户输入

        boolean flag = true;
        while(flag){
            System.out.println("s(show):显示整个队列内容");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头数据");
            
            key=scanner.next().charAt(0);//第一个字符
            switch(key){
                case 's':
                    cq.showQueue();
                    break;
                case 'e':
                    scanner.close();
                    flag=false;
                    break;
                case 'a':
                    System.out.println("请输入要添加的数据");
                    int data=scanner.nextInt();
                    cq.addQueue(data);
                    break;
                case 'g':
                    try {
                        int result= cq.getQueue();
                        System.out.printf("取出的数据是%d\n",result);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int result= cq.headQueue();
                        System.out.printf("队列头数据是%d\n",result);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;                    
            }

        }
        System.out.println("程序退出");
        
    }

    public CircleQueue(int size){
        front=0;
        rear=0;
        maxSize=size;
        arr=new int[maxSize];
    }

    //判断是否为空
    public boolean isEmpty(){
        return front==rear;
    }

    //判断是否已满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }

    //增加一个元素
    public void addQueue(int param){
        if(isFull()){
            System.out.println("队列已满，无法添加");
            return;
        }
        arr[rear]=param;
        rear=(rear+1)%maxSize;//避免超过数组大小
    }

    //弹出队首元素
    public int getQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，队首无元素可弹出");
        }
        int value=arr[front];
        front=(front+1)%maxSize;//避免超过数组大小
        return value;
    }
    
    //查看队首元素
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空，队首无元素可查看");
        }
        return arr[front];
    }

    //展示队列元素
    public void showQueue(){
        if(isEmpty()){
            System.out.println("队列为空");
        }
        for(int i=front;i<(front+size());i++){
            System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
        }
    }

    //计算队列当前元素个数
    public int size(){
        return (rear-front+maxSize)%maxSize;
    }
}