2023-09-22
原文作者:李林超 原文地址: https://www.lilinchao.com/archives/473.html

前言

上篇中,使用数组来模拟队列会出现数组使用一次就不能使用,没有达到复用效果的问题,本篇通过数组 模拟环形队列 来解决该问题。

概述

数组模拟环形队列

对前面的数组模拟队列的优化,充分利用数据,因此将数组看做是一个环形的。(通过取模的方式来实现即可)

分析说明:

  1. 尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(rear+1)%maxSize==front [满] > > 2. rear==front[空]

分析示意图:

202309222128377361.png

思路如下:

  1. front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值等于0. > > 2. rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定,rear的初始值等于0 > 3. 当队列满时,条件是(rear+1)%maxSize==front【满】 > 4. 当队列为空时,rear==front【空】 > 5. 队列中有效的数据的个数:(rear+maxSize-front)%maxSize //rear=1 front=0

在原来的队列上修改得到一个环形队列。

代码

    public class CircleArrayQueueDemo {
        public static void main(String[] args) {
            //创建一个队列
            CircleArray queue= new CircleArray(4);//说明:设置4,其队列的有效 数据最大是3
            char key=' ';//接收用户输入
            Scanner scanner = new Scanner(System.in);
            boolean loop = true;
            //输出一个菜单
            while(loop){
                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':
                        queue.showQueue();
                        break;
                    case 'a':
                        System.out.println("输出一个数");
                        int value = scanner.nextInt();
                        queue.addQueue(value);
                        break;
                    case 'g'://取出数据
                        try{
                            int res = queue.getQueue();
                            System.out.printf("取出的数据是%d\n",res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'h'://查看队列头的数据
                        try {
                            int res = queue.headQueue();
                            System.out.printf("队列头的数据是%d\n",res);
                        }catch (Exception e){
                            System.out.println(e.getMessage());
                        }
                        break;
                    case 'e'://退出
                        scanner.close();
                        loop=false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出!");
        }
    }
    
    class CircleArray{
        private int maxSize;//表示数组的最大容量
        //front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值等于0.
        private int front;//对列头
        //rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定,rear的初始值等于0
        private int rear;//队列尾
        private int[] arr;//该数据用于存放数据,模拟队列
    
        public CircleArray(int arrMaxSize){
            maxSize = arrMaxSize;
            arr = new int[maxSize];
        }
        //判断队列是否满
        public boolean isFull(){
            return (rear+1)%maxSize == front;
        }
        //判断队列是否为空
        public boolean isEmpty(){
            return rear == front;
        }
        //添加数据到队列
        public void addQueue(int n){
            //判断队列是否满
            if(isFull()){
                System.out.println("队列满,不能加入数据!");
                return;
            }
            //直接将数据加入
            arr[rear]=n;
            //将 rear 后移,这里必须考虑取模
            rear = (rear +1)%maxSize;
        }
        //获取队列的数据,出队列
        public int getQueue(){
            //判断队列是否空
            if(isEmpty()){
                //通过抛出异常
                throw new RuntimeException("队列空,不能取数据");
            }
            //这里需要分析出front是指向队列的第一个元素
            //1.先把front对应的值保留到一个临时变量
            //2. 将front后移,考虑取模
            //3. 将临时保存的变量返回
            int value = arr[front];
            front = (front + 1)%maxSize;
            return value;
        }
        //显示队列的所有数据
        public void showQueue(){
            //遍历
            if(isEmpty()){
                System.out.println("队列为空,没有数据");
                return;
            }
            //思路:从front开始遍历,遍历多少个元素
            for(int i=front;i<front+size();i++){
                System.out.printf("arr[%d]=%d\n",maxSize,arr[i%maxSize]);
            }
        }
        //求出当前队列有效数据的个数
        public int size(){
            return (rear+maxSize-front)%maxSize;
        }
        //显示队列的头数据,注意不要取出数据
        public int headQueue(){
            //判断
            if(isEmpty()){
                throw new RuntimeException("队列空的,没有数据!");
            }
            return arr[front];
        }
    }
阅读全文