[数据结构与算法]4.环形队列

1. 介绍

1）front含义：arr[front]就是队列的一个元素，初始值为0。
2）rear含义：rear指向队列的最后一个元素的最后一个位置，空出一个空间作为约定，初始值为0。
3）表示队列为空：rear == front

4）表示队列为满：(rear + 1) % maxSize == front

5）表示队列有效数据的个数：(rear + maxSize - front) % maxSize

6）代码实现

import java.util.Scanner;

public class CircleArrayQueue {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Queue1 q1 = new Queue1(6);
        System.out.println("1.显示队列");
        System.out.println("2.添加数据");
        System.out.println("3.取出数据");
        System.out.println("4.显示队首");
        System.out.println("5.退出");

        boolean bool = true;
        while(bool) {
            System.out.println("请输入操作：");
            int cin = scan.nextInt();
            if(cin != 1 && cin != 2 && cin != 3 && cin != 4 && cin != 5){
                System.out.println("输入有误，请重新输入！");
            }else{
                switch (cin) {
                    case 1:
                        try{
                            q1.showQueue();
                        }catch(Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 2:
                        System.out.println("请输入一个数字：");
                        int value = scan.nextInt();
                        q1.addQueue(value);
                        break;
                    case 3:
                        System.out.println("取出的数据为：" + q1.removeQueue());
                        break;
                    case 4:
                        try{
                            System.out.println("队首元素是：" + q1.showHeadQueue());
                        }catch(Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 5:
                        scan.close();
                        bool = false;
                }
            }
        }
        System.out.println("程序退出~~");
    }
}
class Queue1{
    private int maxSize;
    private int front;
    private int rear;
    private int arr[];

    //构造器
    public Queue1(int size) {
        maxSize = size; //队列容量
        front = 0; //头指针
        rear = 0; //尾指针
        arr = new int[maxSize]; //模拟队列的数组
    }

    //环形队列为空
    public boolean empty(){
        return front == rear;
    }

    //环形队列为满
    public boolean full(){
        return (rear + 1) % maxSize == front; //取模
    }

    //队列中有效数据个数
    public int dataNumber(){
        return (rear + maxSize - front) % maxSize; //取模
    }

    //查询环形队列
    public void showQueue(){
        //判断队列是否为空
        if(empty()){
            throw new RuntimeException("队列为空~~");
        }
        for(int i = front; i < front + dataNumber();i++){
            int j = i % maxSize; //取模，让数据始终在一个环形队列中添加和取出
            System.out.println("arr[" + j + "] = " + arr[j]);
        }
    }

    //添加数据
    public void addQueue(int data){
        //判断队列是否为满
        if(full()){
            System.out.println("队列已满~~");
            return;
        }
        arr[rear] = data; //向尾指针所指向的位置赋值
        rear = (rear + 1) % maxSize; //尾指针后移，尾指针始终指向最后一个数据的下一个位置
    }

    //取出数据
    public int removeQueue(){
        //判断队列是否为空
        if(empty()){
            throw new RuntimeException("队列为空~~");
        }
        int value = arr[front]; //将头指针指向的数据赋值给一个临时变量
        front = (front + 1) % maxSize; //头指针后移，取模
        return value; //返回临时变量
    }

    //查询队首元素
    public int showHeadQueue(){
        //判断队列是否为空
        if(empty()){
            throw new RuntimeException("队列为空~~");
        }
        return arr[front]; //直接返回头指针指向的数据
    }
}