[数据结构与算法]数据结构-环形队列-02

数据结构-环形队列02

环形队列思路：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RZcJRIGR-1639060711477)(C:\Users\Admin\AppData\Roaming\Typora\typora-user-images\image-20211209214325545.png)]

1、front变量的含义：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值为0

2、rear变量的含义：rear指向队列的最后一个元素的后一位，因为希望空出一个空间做为约定，rear的初始值为0

3、当队列满时，条件时（rear+1）%maxsize == front （这里之所以判断rear+1，是因为rear为索引值，而maxsize为长度）

4、对队列为空的条件 rear==front

5、当我们这样分析，队列中的有效的数据的个数：（rear+maxsize-front）%maxsize

6、我们就可以在原来的队列上修改得到，一个环形队列

实现一个环形数组：

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        CircleQueue circleQueue = new CircleQueue(3);
        char key =' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop){
            System.out.println("s(show):显示列表");
            System.out.println("a(add):添加数据到列表");
            System.out.println("g(getQueue):从列表中取出数据");
            System.out.println("d(headQueue):显示头元素");
            System.out.println("e(exit):程序退出");
            key = scanner.next().charAt(0);
            switch (key){
                case 's':
                    circleQueue.show();
                    break;
                case 'a':
                    System.out.println("请输入一个数");
                    int nextInt = scanner.nextInt();
                    circleQueue.add(nextInt);
                    break;

                case 'g':

                    int res = circleQueue.getQueue();

                    System.out.println("取出的数："+res);
                    break;

                case 'h':
                    int res1 = circleQueue.headQueue();
                    System.out.println("取出的数："+res1);
                    break;

                case 'e':
                    scanner.close();
                    loop = false;
                    break;

                default:
                    break;
            }

        }

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

class CircleQueue{
    //定义变量
    int front;
    int rear;
    int[] array;
    int maxsize;

    //构造一个队列
    public CircleQueue(int max){
        maxsize = max;
        array = new int[maxsize];
    }

    //获取队列中的有效数字的个数
    public int getsize(){
        return (rear+maxsize-front)%maxsize;
    }

    //判断队列是否满
    public boolean isfull(){
        return (rear+1)%maxsize == front;
    }

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

    //添加数据到队列中
    public void add(int n){
        //添加前判断队列是否满
        if (isfull()){
            System.out.println("队列已满，不能再添加数据");
        }
        array[rear] = n;
        //数据添加完后 rear后移  这个时候就需要取模，完成循环赋值
        rear = (rear+1)%maxsize;
    }

    public  int getQueue(){
        if (isEmpty()){
            System.out.println("队列为空，不能取出数据");     //取出数据时建议使用try  catch来使用，因为当队列中没有数据时，会导致后面的打印代码
            //依旧打印数据
        }
        int value = array[front];
        front = (front+1)%maxsize;
        return value;
    }

    //打印数组
    public void show(){
        for (int i = front; i <front+getsize() ; i++) {
            System.out.println("array["+i%maxsize+"]："+i%maxsize+" "+array[i%maxsize]);
        }
    }

    //显示头元素
    public int headQueue(){
        if (isEmpty()){
            System.out.println("队列为空，没有数据");

        }
        return array[front];
    }
}