循环队列如何判断队满与队空？

Question

在实现循环队列时，如何准确判断队列为空或为满是一个关键问题。由于队头（front）和队尾（rear）指针在循环移动，当 `front == rear` 时，可能表示队空，但也可能在队满时出现相同情况，造成歧义。常见的解决方案有三种：牺牲一个存储单元、增设长度计数器、或使用标志位区分队空队满。请结合具体实现方式，分析各种方法的优缺点及在实际应用中的适用场景。

Answer 1

循环队列中判断队空与队满的三种策略深度解析

在数据结构设计中，循环队列（Circular Queue）因其高效的内存利用和时间复杂度优势，被广泛应用于操作系统、网络缓冲区、实时系统等场景。然而，其核心挑战之一是如何准确区分“队列为空”和“队列为满”的状态——当 front == rear 时，这一条件既可能表示队列为空，也可能表示队列已满，从而产生歧义。

1. 问题背景：为何会出现 front == rear 的歧义？

循环队列通过模运算实现指针的循环移动。设队列容量为 N，使用数组存储元素，front 指向队首元素，rear 指向下一个可插入位置。初始时两者均为0：

• 入队操作：queue[rear] = x; rear = (rear + 1) % N;
• 出队操作：x = queue[front]; front = (front + 1) % N;

当执行若干操作后，可能出现以下两种情况均满足 front == rear：

状态	front 值	rear 值	含义
队空	3	3	无元素
队满	3	3	N-1个元素已存入，rear追上front

因此，必须引入额外机制消除歧义。

2. 解决方案一：牺牲一个存储单元法

该方法规定队列最大实际容量为 N - 1，即不允许真正填满所有N个槽位。通过限制 (rear + 1) % N != front 来避免满队时 front == rear。

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} CircularQueue;

// 判断队空
int is_empty(CircularQueue *q) {
    return q->front == q->rear;
}

// 判断队满
int is_full(CircularQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

优点在于实现简单，无需额外变量；缺点是空间利用率降低约1/(N)，对小容量队列影响显著。

3. 解决方案二：增设长度计数器

维护一个额外的 size 或 count 变量，记录当前元素数量，直接通过该值判断状态。

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
    int size;  // 当前元素个数
} CountedQueue;

int is_empty(CountedQueue *q) { return q->size == 0; }
int is_full(CountedQueue *q)  { return q->size == MAX_SIZE; }

void enqueue(CountedQueue *q, int x) {
    if (is_full(q)) return;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->size++;
}

void dequeue(CountedQueue *q) {
    if (is_empty(q)) return;
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
}

此方法逻辑清晰，空间利用率高，适合多线程环境或性能敏感系统，但增加了维护开销。

4. 解决方案三：使用标志位区分状态

引入布尔标志 full_flag，仅在队列曾被写满时置位，结合 front == rear 进行判断。

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
    int full;  // 标志位：1表示满，0表示不确定
} FlaggedQueue;

int is_empty(FlaggedQueue *q) { 
    return q->front == q->rear && !q->full; 
}

int is_full(FlaggedQueue *q) { 
    return q->full; 
}

void enqueue(FlaggedQueue *q, int x) {
    if (is_full(q)) return;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
    if (q->rear == q->front)
        q->full = 1;
}

void dequeue(FlaggedQueue *q) {
    if (is_empty(q)) return;
    q->front = (q->front + 1) % MAX_SIZE;
    q->full = 0;  // 出队后一定不满
}

该方式节省空间且不牺牲容量，但状态转移较复杂，易出错，适用于嵌入式等资源受限场景。

5. 各方案对比分析

方案	空间利用率	实现复杂度	同步友好性	适用场景
牺牲单元	≈99% (大N)	低	高	教学、小型系统
长度计数器	100%	中	需原子操作	高性能服务器、并发系统
标志位法	100%	较高	中	嵌入式、RTOS

6. 实际应用中的选择考量

在Linux内核的kfifo实现中，采用的是“长度计数器+幂次对齐”策略，兼顾效率与安全性。而在FreeRTOS的队列实现中，则根据配置灵活支持多种模式。现代高性能中间件如ZeroMQ、DPDK中，常结合内存池与无锁队列技术，底层仍依赖上述基本判据。

mermaid流程图展示判断逻辑分支：

graph TD
    A[front == rear?] -- 是 --> B{是否使用标志位?}
    B -- 是 --> C[检查full标志]
    B -- 否 --> D{是否允许满N?}
    D -- 否 --> E[视为队空]
    D -- 是 --> F[视为队满]
    A -- 否 --> G[非空非满]

综上所述，三种方法各有侧重，在架构设计阶段应基于性能需求、资源约束和并发模型综合权衡。