基于 Java 实现的环形数组队列详解

1. 环形数组队列简介

队列（Queue）是一种常用的线性数据结构，具有先进先出（FIFO）的特点。在传统的线性队列中，随着出队操作，队列前端会出现空闲空间，但这些空间无法重复使用，导致浪费。为了解决这个问题，我们可以采用环形数组队列。

环形数组队列的特点

环形队列通过逻辑上的首尾相连，借助取模运算，形成循环效果，具备以下特点：

1. 高效利用数组空间，避免传统线性队列中“假溢出”问题。
2. 简单易用，通过简单的指针和取模运算实现。

但在环形队列中，区分“队列空”和“队列满”的状态需要特殊设计，这也是本文重点说明的内容。

2. 关键设计：为什么需要空出一个位置？

在环形队列中，头指针（front）和尾指针（rear）会随着入队和出队操作不断移动，并且会通过取模运算回绕。当队列中所有位置都被占满时，头尾指针的关系是：

rear == front

这与队列为空时的条件一致，因此无法直接区分“队列满”和“队列空”的状态。

具体效果如下所示：

解决方案：空出一个位置
为了避免这种冲突，我们在设计时让环形队列空出一个位置，即当尾指针 rear 的下一步移动与头指针 front 重合时，视为队列已满。

因此：

• 队列为空：front == rear
• 队列已满：(rear + 1) % maxSize == front

注意：环形队列的实际容量为 maxSize - 1。

示例：
假设队列大小为 4，实际可用空间为 3：

• 初始状态：front = 0, rear = 0，队列为空。
• 当 rear 指针移动到与 front 前一个位置时，即 rear = 3，队列满。

3. 队列的核心操作详解

3.1 入队操作（push）

步骤：

1. 检查队列是否已满：(rear + 1) % maxSize == front。
2. 如果未满：
   • 将元素插入到 rear 指针位置。
   • 更新 rear 指针：rear = (rear + 1) % maxSize。

示例：
假设 maxSize = 4：

• 初始状态：front = 0, rear = 0，数组为 [0, 0, 0, 0]。
• 入队 1：
  • 插入位置：rear = 0，数组变为 [1, 0, 0, 0]。
  • 更新 rear = (0 + 1) % 4 = 1。

连续入队 2, 3 后：

数组: [1, 2, 3, 0]
指针: front = 0, rear = 3

此时尝试入队 4 时：

• (rear + 1) % maxSize == front -> (3 + 1) % 4 == 0，队列已满。

3.2 出队操作（pop）

步骤：

1. 检查队列是否为空：front == rear。
2. 如果不为空：
   • 读取 front 指针位置的数据。
   • 更新 front 指针：front = (front + 1) % maxSize。

示例：

• 初始状态：front = 0, rear = 3，数组为 [1, 2, 3, 0]。
• 出队一次：
  • 读取位置：front = 0，返回值为 1。
  • 更新 front = (0 + 1) % 4 = 1。

出队两次后：

数组: [1, 2, 3, 0]
指针: front = 2, rear = 3

此时可以继续入队，利用数组前端的空闲位置。

3.3 队列的状态判断

队列为空的条件：

front == rear

当头尾指针重合时，队列为空。

队列已满的条件：

(rear + 1) % maxSize == front

当尾指针的下一步移动会与头指针重合时，队列满。

3.4 环形队列状态变化示例

假设 maxSize = 4，以下是完整的操作流程：

初始状态：

数组: [0, 0, 0, 0]
指针: front = 0, rear = 0
状态: 队列为空

入队三个元素：

数组: [1, 2, 3, 0]
指针: front = 0, rear = 3
状态: 队列未满

尝试入队第四个元素：

• 判断条件：(rear + 1) % maxSize == front
• 此时 (3 + 1) % 4 == 0 -> 队列已满

出队两个元素：

数组: [1, 2, 3, 0]
指针: front = 2, rear = 3
状态: 队列未满

再次入队一个元素（实现循环）：

• 插入位置：rear = 3，更新 rear = (3 + 1) % 4 = 0。

数组: [4, 2, 3, 0]
指针: front = 2, rear = 0
状态: 队列未满

4. 核心代码实现

以下是实现环形数组队列的核心代码，简化版：

package com.algorithm.dev.queue;

import java.util.Scanner;

/**
 * @author xiazhihao
 * @ClassName: CircleArrayQueue
 * @ClassNameExplain:
 * @Description: 环形数组队列
 * @date 2024/12/11 14:33
 */
public class CircleArrayQueue {

    /**
     * 最大值
     */
    private int maxSize;

    /**
     * 头部指针
     */
    private int front;

    /**
     * 尾部指针
     */
    private int rear;

    /**
     * 具体存数组值的地方
     */
    private int[] data;

    /**
     * 实例化
     * @param size 环形数组容量
     */
    public CircleArrayQueue(int size){
        this.maxSize = size;
        this.data = new int[size];
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 入队
     * @param source 数据源
     */
    public void push(int source){
        //判断是否已经满了
        if (isFull()){
            throw new RuntimeException("队列已满");
        }
        //
        this.data[rear] = source;
        //st得保证后续rear+1
        //st保证rear不超过临界但是需要回滚到下面
        /**
         * ex
         * 0  <- rear                  1   <- front
         * 1  <- front   -> 入队 1      1
         * 0                           0   <- rear
         */
        rear = (rear+1)%maxSize;
    }

    /**
     * 出队
     * @return 出队的数据
     */
    public int pop(){
        //st判空为空不取值
        if (isEmpty()){
            throw new RuntimeException("队列已空");
        }
        /**
         * ex
         * 1  <- front                0
         * 0             -> 出队       0
         * 0  <- rear                 0   <- rear <- front
         */
        //出队取值
        int temp = data[front];
        //st出队也是front+1
        front = (front+1)%maxSize;
        //st注意出队的极限
        return temp;
    }

    /**
     * 是否为空
     * @return 空是true
     */
    public boolean isEmpty(){
        /**
         * 指一起肯定是空的 因为有一个值rear会+1
         */
        return front == rear;
    }

    /**
     * 是否已满
     * @return 已满true
     */
    public boolean isFull(){
        /**
         * ex
         *   <- rear
         * 1             特殊的环形的情况 =>       1  <- front
         * 1 <- front                           1  <- rear
         */
        //正常思考 如果是正常应该判断 2-0 = 2 = maxsize - 1 就行本质是知道占据了多少位

        //环形不行 因为 存在大小问题 比如 0 - 1 =  -1 但是如果是负数的话 其实 maxsize - 1 = 2 也能判断出暂居了3位

        //这种情况可用巧用取模算法 加上缺失的其实就是减法 而正数可以后面使用取模消除多余的结果

        //return (maxSize-1) == (rear - front + maxSize) % maxSize;

        //更容易理解的算法  其实rear在极限的情况下就是暂了空位的位置 空位在接下来还需要填满+1 代表就真的满了
        return front == (rear + 1) % maxSize;

    }

    /**
     * 获取具体的数控
     * @return siez
     */
    public int size(){
        // 思考isFull的算法是怎么做的 道理相似
        return ((rear - front + maxSize) % maxSize);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入环形队列的大小（注意有效容量是大小-1）：");
        int size = scanner.nextInt();
        CircleArrayQueue queue = new CircleArrayQueue(size);

        while (true) {
            System.out.println("\n请选择操作：");
            System.out.println("1. 入队 (push)");
            System.out.println("2. 出队 (pop)");
            System.out.println("3. 查看队列是否为空 (isEmpty)");
            System.out.println("4. 查看队列是否已满 (isFull)");
            System.out.println("5. 查看队列中的元素个数 (size)");
            System.out.println("6. 退出 (exit)");
            System.out.print("请输入操作编号：");

            int choice = scanner.nextInt();

            try {
                switch (choice) {
                    case 1:
                        System.out.print("请输入要入队的元素：");
                        int value = scanner.nextInt();
                        queue.push(value);
                        System.out.println("入队成功！");
                        break;

                    case 2:
                        int poppedValue = queue.pop();
                        System.out.println("出队元素：" + poppedValue);
                        break;

                    case 3:
                        System.out.println(queue.isEmpty() ? "队列为空" : "队列不为空");
                        break;

                    case 4:
                        System.out.println(queue.isFull() ? "队列已满" : "队列未满");
                        break;

                    case 5:
                        System.out.println("当前队列中的元素个数：" + queue.size());
                        break;

                    case 6:
                        System.out.println("程序已退出！");
                        scanner.close();
                        return;

                    default:
                        System.out.println("无效的操作编号，请重新输入！");
                        break;
                }
            } catch (Exception e) {
                System.out.println("操作失败：" + e.getMessage());
            }
        }
    }

}

5. 总结

5.1 设计亮点

1. 空出一个位置：
   通过空出一个位置区分“队列满”和“队列空”，避免状态冲突。
2. 取模运算：
   通过 (index + 1) % maxSize 实现指针的循环移动。

5.2 实际容量计算

环形队列的实际容量为 maxSize - 1，在初始化时应根据需求预留足够的空间。

环形数组队列是一种高效的数据结构，通过合理的设计，充分利用了有限的数组空间，适合在缓存管理、任务调度等场景中应用。