循环数组队列isFull方法最优实现方式探讨及实现疑问

嘿，我来帮你梳理下循环数组队列（Circular Array Queue）中isFull方法的最优实现思路，先说说你当前代码可能存在的问题，再给出两种常用的高效方案～

先聊聊你当前实现的问题 #

你写的这段代码：

@Override 
public boolean isFull() { 
    return ((rear-front) == -1 || (rear-front) == (size - 1)) ? true : false; 
}

逻辑上存在漏洞哦。举个典型反例：假设队列的数组容量是5（size=5），当你出队几次后，front=4、rear=0，这时候队列里只有1个元素，但rear-front=-1，你的代码会误判队列已满。问题根源在于没有考虑循环数组的取模特性，单纯用rear-front的差值判断，会把“队列有少量元素且rear在front前面”的情况当成满队列。

两种最优实现方案 #

循环数组队列区分空和满，通常有两种经典且高效的实现方式，都是O(1)时间复杂度，属于最优方案：

方案1：浪费一个数组空间（无额外计数器） #

这种方式最节省内存，不需要额外维护元素计数变量。核心思路是故意留一个数组位置不用，用(rear + 1) % capacity == front作为满队列的判断条件，而空队列的条件是rear == front。

实现代码示例：

private int[] queue;
private int front; // 队头指针
private int rear;  // 队尾指针（指向队尾元素的下一个位置）
private int capacity; // 数组容量

@Override
public boolean isFull() {
    return (rear + 1) % capacity == front;
}

// 对应的isEmpty方法
public boolean isEmpty() {
    return rear == front;
}

这种方式通过牺牲一个数组位置，完美区分了空队列和满队列的状态，逻辑严谨且内存占用低。

方案2：维护一个元素计数器（更直观） #

如果不想浪费数组空间，可以额外维护一个count变量记录当前队列中的元素个数。这时候满队列的判断就非常简单直接：count == capacity。

实现代码示例：

private int[] queue;
private int front;
private int rear;
private int capacity;
private int count; // 当前元素个数

@Override
public boolean isFull() {
    return count == capacity;
}

// 对应的isEmpty方法
public boolean isEmpty() {
    return count == 0;
}

这种方式的优点是逻辑清晰，几乎不会出错，对新手友好；唯一的小缺点是多占用了一个int变量的内存，不过通常可以忽略不计。

怎么选？ #

• 如果对内存占用要求极高，优先选方案1（浪费一个空间的方式）；
• 如果更看重代码的可读性和维护性，优先选方案2（计数器方式）。

两种方式都是时间复杂度O(1)的最优实现，根据你的业务场景选择即可～

内容的提问来源于stack exchange，提问作者Alessandro Petric