每日科普 · 2026-10-13 周二

考研 408 × 求职面试

知识点 · 数据结构 · 进阶

循环队列的判空与判满

循环队列用一维数组存放元素，front指向队头，rear通常指向队尾的下一个空位。入队时data[rear]=x，rear=(rear+1)%MaxSize；出队时front=(front+1)%MaxSize。关键难点是front与rear会绕回，单看二者相等无法区分空和满。常用方案有三种：
1. 牺牲一个存储单元：队列最多放MaxSize-1个元素。判空：front==rear；判满：(rear+1)%MaxSize==front。优点是实现简单，考研和笔试最常见。
2. 增加count变量：入队count++，出队count--。判空count==0，判满count==MaxSize，不浪费单元。
3. 增加tag标记：当front==rear时，若tag=0表示空，tag=1表示满；入队置1，出队置0。
务必注意rear的定义。若rear指向队尾元素而不是下一位置，判空判满表达式会变。答题时先说明约定，再写公式。

每日一题 · 数据结构

循环队列的判空与判满

循环队列采用“牺牲一个存储单元”法区分队空和队满，数组容量MaxSize=8。当前front=5，rear=4，则下列判断正确的是：
A. 队空
B. 队满
C. 元素个数为0
D. 元素个数为8

解析

判空条件front==rear，这里5!=4，不空。判满条件(rear+1)%MaxSize==front，即(4+1)%8=5==front，所以队满。元素个数=(rear-front+MaxSize)%MaxSize=(4-5+8)%8=7，正好等于最大容量MaxSize-1=7。故选B。C、D不符。

面试小贴士 · 数据结构

循环队列的判空与判满

先说明rear指向队尾后一位置和采用哪种判满方案。牺牲单元法：空front==rear，满(rear+1)%N==front；计数法：空count==0，满count==N。易错点是不取模、把满条件写成rear+1==front，或忘记实际容量是N-1。

代码实现 · C

代码示例

#include <stdio.h>
#define MAX 6
typedef struct { int data[MAX]; int front, rear; } Queue;

void init(Queue *q) { q->front = q->rear = 0; }
int empty(Queue *q) { return q->front == q->rear; }
int full(Queue *q) { return (q->rear + 1) % MAX == q->front; }
int enqueue(Queue *q, int x) {
    if (full(q)) return 0;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX;
    return 1;
}
int dequeue(Queue *q, int *x) {
    if (empty(q)) return 0;
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAX;
    return 1;
}
int main() {
    Queue q; init(&q);
    printf("empty=%d full=%d", empty(&q), full(&q));
    enqueue(&q, 1); enqueue(&q, 2);
    printf("empty=%d full=%d", empty(&q), full(&q));
    return 0;
}