队列数据结构详解：从数组模拟到环形队列的优化实现

队列是计算机科学中最基础且应用广泛的数据结构之一。无论是在操作系统的任务调度、消息队列中间件，还是在图的广度优先搜索算法中，队列都扮演着至关重要的角色。本文将从一个具体的应用场景出发，逐步讲解队列的概念，并深入探讨如何使用数组在 Java 中模拟队列，最终引出环形队列的优化思路与代码实现。

1. 队列的应用场景

队列常被用于处理需要“排队”的场景。例如，银行排队叫号系统、打印机任务队列、消息中间件等。在这些场景中，数据需要按照先来先处理的规则被消费，这就需要一种能够支持这种规则的数据结构。

2. 队列是什么？

队列是一种有序列表，可以用数组或链表来实现。它遵循 先入先出（FIFO，First In First Out） 的原则：先存入队列的数据，必须先被取出。

使用数组来模拟队列时，通常会维护一个数组用于存储数据，以及两个指针（或索引）：一个指向队列头部的 front，一个指向队列尾部的 rear。其基本工作方式可由下图示意：

队列示意图

初始状态：队列为空，front 与 rear 均指向某个初始位置（一般设置为 -1）。
入队操作：存入一个数据时，尾指针 rear 向后移动，头指针 front 不动。
出队操作：取出一个数据时，头指针 front 向后移动，尾指针 rear 不动，符合先进先出的逻辑。

3. 队列的实现（数组模拟队列）

基于上述思想，我们可以设计一个 ArrQueue 类来用数组模拟队列。

实现思路：

创建一个队列类。
在类内部维护一个数组用于存放数据，一切方法的实现都围绕数组的特性展开。
通过 front 和 rear 两个指针的移动来模拟数据的增删。初始时，设定 front = -1，rear = -1。

3.1 基本属性与构造器

public class ArrQueue {
    private int maxSize;   // 数组的最大容量
    private int front;     // 队列头指针
    private int rear;      // 队列尾指针
    private int[] arr;     // 存放数据的数组

    // 构造器
    public ArrQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // 指向队列头部的前一个位置
        rear = -1;  // 指向队列尾部的数据
    }
}

3.2 判断队列状态

// 判断队列是否已满
public boolean isFull() {
    return rear == maxSize - 1;
}

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

3.3 入队与出队

// 添加数据到队列
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];
}

3.4 查看队列信息

// 显示队列中的所有数据
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];
}

3.5 测试与问题发现

编写一个简单的菜单程序测试该队列：

1 2	ArrQueue queue = new ArrQueue(3); // ... 菜单逻辑：show, add, get, head, exit

在测试过程中，我们发现了两个明显的问题：

“假取出”现象：连续执行 get 和 show 时，数据似乎并未被真正移除，只是在代码逻辑上标记为“已取出”，数组中的元素仍然保留。
“一次性”队列：当所有数据被取出后，front 和 rear 都停留在高位，即便数组前方已空，也无法再添加新数据。这并不符合实际使用的需求——队列应当能够循环利用空间。

这些问题的本质是空间无法复用，也就是我们常说的“假溢出”。为了解决这个问题，环形队列应运而生。

4. 队列的再实现：数组模拟环形队列

环形队列的核心理念是将线性的数组在逻辑上看作一个首尾相接的环，通过取模运算（%）让 front 和 rear 指针能够在数组的边界处“折返”，从而实现空间的循环利用。

4.1 环形队列的设计思路

我们对指针的含义和判空判满条件进行如下调整：

front 直接指向队列的第一个有效元素，初始值为 0。
rear 指向队列中下一个准备存放数据的位置，初始值为 0。
队列为空的条件保持不变：rear == front。
队列为满的条件改为：(rear + 1) % maxSize == front。也就是说，数组中会预留一个空位作为“隔离区”，一旦 rear 再前进一步就会追上 front，我们便认为队列已满。这是一种逻辑满而非物理满——最大有效数据个数为 maxSize - 1。
有效数据个数的计算公式为：(rear - front + maxSize) % maxSize。当 rear 位于 front 后面（未折返）时，rear - front 为正数，公式结果即为实际个数；当 rear 折返到 front 前面时，rear - front 为负数，加上 maxSize 后取模，即可得到正确的元素数目。

下面用图解来直观地展示环形队列的工作方式。约定 maxSize = 4，数组下标为 0、1、2、3。

初始时 front = rear = 0，队列为空。
入队操作：在 rear 位置存入数据，然后执行 rear = (rear + 1) % maxSize，让 rear 顺时针移动。
出队操作：从 front 位置取出数据，然后执行 front = (front + 1) % maxSize，front 同样顺时针移动。

需要特别注意的是：

rear 指向的空位会作为预留的隔离区，并且这个空位会随着操作在环形上动态移动。
判满条件 (rear + 1) % maxSize == front 确保了至少会有一个位置不被占用，从而能明确区分队列空和队列满的状态。

4.2 环形队列的代码实现（关键差异部分）

public class CircleArrayQueue {
    private int maxSize;
    private int front;   // 指向第一个有效元素，初始0
    private int rear;    // 指向下一个空位，初始0
    private int[] arr;

    public CircleArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        // front 和 rear 默认为0，无需再设
    }

    // 判断是否【逻辑满】
    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;      // rear后移，若越界则归零
    }

    // 取出数据
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法取出数据");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;    // front后移，若越界则归零
        return value;
    }

    // 显示队列中所有有效元素
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
            return;
        }
        int size = (rear - front + maxSize) % maxSize;
        for (int i = 0; i < size; i++) {
            int index = (front + i) % maxSize;
            System.out.printf("arr[%d] = %d\n", index, arr[index]);
        }
    }

    // 显示队列头部数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据");
        }
        return arr[front];
    }
}