数组模拟环形队列实现

╰半橙微兮° 2023-09-27 08:13 17阅读 0赞

### 一、队列（Queue） ###

1）特点：**先进先出**，即：先存入队列的数据，要先取出，后存入的要后取出  
2）是一个有序列表，可以用数组或是链表来实现  
3）示意图（使用数组模拟队列示意图）  
![在这里插入图片描述][abdd6545dd834ae4a36f076cefeb0079.png]  
添加数据是在队列的尾部加，front值不变  
取数据的时候是从队列的头部取，rear值不变，front值依次递减

### 二、使用数组模拟队列思路 ###

1、因为队列的输入、输出是分别从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的下标，front会随着数据输入而改变，而rear则是随着数据的输入而改变。

2、向队列中添加数据的思路分析：  
1）当front == rear，表示队列为空，将尾部指针往后移动一位，即rear+1  
2）若尾指针rear小于队列的最大下标 maxSize - 1,则表示队列未满，则可以将数据存放到队列中，否则无法存入数据。rear == maxSize - 1\[队列已满\]

### 三、代码实现 ###

/**
     * 使用数组模拟队列
     */
    class ArrayQueue {
        
        /**
         * 数组最大容量
         */
        private int maxSize;
        /**
         * 数组头
         */
        private int front;
        /**
         * 数组尾
         */
        private int rear;
        /**
         * 存放数据的数组
         */
        private int[] arr;
    
        /**
         * 创建队列的构造器
         */
        public ArrayQueue(int maxSize) {
        
            this.maxSize = maxSize;
            // 指向队列头部的前一个位置
            this.front = -1;
            // 指向队列尾的具体位置
            this.rear = -1;
            this.arr = new int[maxSize];
        }
    
        /**
         * 判断队列是否已满
         */
        public boolean isFull() {
        
            return rear == maxSize - 1;
        }
    
        /**
         * 判断队列是否为空
         */
        public boolean isEmpty() {
        
            return rear == front;
        }
    
        /**
         * 向队列添加数据
         */
        public void addQueue(int n) {
        
            // 首先判断队列是否已满
            if (isFull()) {
        
                System.out.println("队列已满，不能再添加数据~");
                return;
            }
            rear++;
            arr[rear] = n;
        }
    
        /**
         * 获取队列的数据,出队列
         */
        public int getQueue() {
        
            // 首先判断队列是否为空
            if (isEmpty()) {
        
                throw new RuntimeException("队列为空~");
            }
            // 出队列，是从队列的头开始
            front++;
            return arr[front];
        }
    
        /**
         * 显示队列数据
         */
        public void showQueue() {
        
            // 首先判断队列是否为空
            if (isEmpty()) {
        
                System.out.println("队列为空");
                return;
            }
            for (int i = 0; i < arr.length; i++) {
        
                System.out.printf("arr[%d]=%d\n", i, arr[i]);
            }
        }
    
        /**
         * 显示队列头部数据
         */
        public int headQueue() {
        
            if (isEmpty()) {
        
                throw new RuntimeException("队列为空~");
            }
            return arr[front + 1];
        }
    
    }

问题分析并优化  
**1）缺点：目前这种队列的方式有一个弊端，队列使用一次就不能再使用了。**  
**2）将这个数组使用算法，改进成一个环形队列，取模：%**

### 四、数组模拟环形队列 ###

#### 4.1、思路： ####

![在这里插入图片描述][f7192ad30b934b14a0daa79c559e1e60.png]

#### 4.2 代码实现 ####

class CircleQueue {
        
        /**
         * 数组最大容量
         */
        private int maxSize;
        /**
         * 数组头: 指向队列的第一个元素，初始值为0
         */
        private int front;
        /**
         * 数组尾：指向队列的最后一个元素的后一个位置，默认值为0
         */
        private int rear;
        /**
         * 存放数据的数组
         */
        private int[] arr;
    
        public CircleQueue(int maxSize) {
        
            this.maxSize = maxSize;
            this.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()) {
        
                throw new RuntimeException("队列已满，不能存放数据！");
            }
            arr[rear] = n;
            rear = (rear + 1) % maxSize;
        }
    
        /**
         * 获取队列的数据，出队列
         *
         * @return
         */
        public int getQueue() {
        
            // 首先判断队列是否为空
            if (isEmpty()) {
        
                throw new RuntimeException("队列为空，不能取出数据！");
            }
            /**
             * 取元素的逻辑：
             * 1、front是指向队列的第一个元素，先将第一个元素取出放到临时变量中保存
             * 2、front向后移动一位，front = (front + 1) % maxSize
             * 3、最后返回第一步的临时变量
             */
            int tmp = arr[front];
            front = (front + 1) % maxSize;
            return tmp;
        }
    
        /**
         * 显示队列的所有数据
         */
        public void showQueue(){
        
            if(isEmpty()){
        
                System.out.println("队列为空，不能取出数据！");
                return;
            }
            /**
             * 遍历队列的思路：
             * 从front位置开始，遍历(rear+maxSize-front)%maxSize个元素
             */
            int length = (rear + maxSize - front) % maxSize;
            for (int i = front; i < length + front; i++) {
        
                System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
            }
        }
        
    }

[abdd6545dd834ae4a36f076cefeb0079.png]: https://img-blog.csdnimg.cn/abdd6545dd834ae4a36f076cefeb0079.png
[f7192ad30b934b14a0daa79c559e1e60.png]: https://img-blog.csdnimg.cn/f7192ad30b934b14a0daa79c559e1e60.png