第六章：队列与循环队列——从排队买票到环形缓冲区

队列这东西，说白了就是「先来后到」。我刚开始学数据结构时，觉得队列不就是个排队吗？有啥好讲的。直到我在一个嵌入式项目里，因为队列的假溢出问题导致系统死锁，才真正明白——队列的水，比你想象的要深。

6.1 队列的顺序存储与假溢出问题

队列的顺序存储，就是用数组来实现。两个指针：front 指向队头，rear 指向队尾。入队时 rear++，出队时 front++。听起来很简单对吧？

但问题来了。你想想看，如果 front 一直往后移，前面的空间就空出来了。rear 到了数组末尾，明明前面还有空位，却不能再入队了。这就是经典的「假溢出」。

我曾经在一个数据采集系统中遇到过这个问题。采集卡不断往队列里塞数据，处理线程从队头取。跑了几个小时，突然发现队列满了——但实际存储的数据量只有数组容量的一半。排查了半天，就是假溢出在作怪。

6.2 循环队列——解决假溢出的经典方案

循环队列的思路很巧妙：把数组首尾相连，形成一个环。当 rear 到达数组末尾时，下一个位置回到数组开头。

嗯，这里要注意：循环队列的判空和判满，是个经典陷阱。

6.2.1 判空与判满

循环队列中，front 和 rear 的初始值通常都是 0。判空很简单：front == rear。

但判满呢？如果也用 front == rear，那就和判空冲突了。怎么办？

我个人习惯用「牺牲一个存储单元」的方法：

• 判空：front == rear
• 判满：(rear + 1) % maxSize == front

也就是说，队列最多只能存 maxSize - 1 个元素。那个空出来的位置，就是用来区分空和满的。

// 循环队列核心操作
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
} CircularQueue;

// 初始化
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
}

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

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

// 入队
int enQueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        return -1;  // 队列已满
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return 0;
}

// 出队
int deQueue(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        return -1;  // 队列为空
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return 0;
}

6.3 链式队列——动态扩容的另一种选择

循环队列虽然解决了假溢出，但数组大小是固定的。如果你不知道数据量有多大，或者数据量波动很大，链式队列就更合适。

链式队列本质上是一个单链表，但只允许在队尾插入、队头删除。我习惯用两个指针：front 指向头结点，rear 指向尾结点。

// 链式队列结点
typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;

// 链式队列
typedef struct {
    QNode *front;  // 队头指针
    QNode *rear;   // 队尾指针
} LinkedQueue;

// 入队
void enQueue(LinkedQueue *q, int value) {
    QNode *newNode = (QNode *)malloc(sizeof(QNode));
    newNode->data = value;
    newNode->next = NULL;
    
    if (q->rear == NULL) {
        // 空队列
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队
int deQueue(LinkedQueue *q, int *value) {
    if (q->front == NULL) {
        return -1;  // 空队列
    }
    QNode *temp = q->front;
    *value = temp->data;
    q->front = temp->next;
    
    if (q->front == NULL) {
        q->rear = NULL;  // 队列变空
    }
    free(temp);
    return 0;
}

6.4 舞伴配对问题——队列的经典应用

舞伴配对问题，说白了就是：一群男生和一群女生跳舞，每个人按顺序排队。每次从男队和女队各取一个人配对。如果某一队没人了，剩下的人继续等待。

这个问题用队列来解决，简直天造地设。两个队列，一个男队，一个女队。每次从两个队列各出队一个人，配对成功。如果某个队列空了，就等下一轮。

// 舞伴配对
typedef struct {
    char name[20];
    char sex;  // 'M' 或 'F'
} Dancer;

void matchDancers(Dancer dancers[], int n) {
    LinkedQueue maleQueue, femaleQueue;
    initQueue(&maleQueue);
    initQueue(&femaleQueue);
    
    // 按性别分别入队
    for (int i = 0; i < n; i++) {
        if (dancers[i].sex == 'M') {
            enQueue(&maleQueue, dancers[i]);
        } else {
            enQueue(&femaleQueue, dancers[i]);
        }
    }
    
    // 配对
    while (!isEmpty(&maleQueue) && !isEmpty(&femaleQueue)) {
        Dancer male, female;
        deQueue(&maleQueue, &male);
        deQueue(&femaleQueue, &female);
        printf("%s 和 %s 配对\n", male.name, female.name);
    }
    
    // 输出等待的人
    if (!isEmpty(&maleQueue)) {
        printf("还有 %d 位男士在等待\n", queueSize(&maleQueue));
    }
    if (!isEmpty(&femaleQueue)) {
        printf("还有 %d 位女士在等待\n", queueSize(&femaleQueue));
    }
}

6.5 本章知识体系

下面这张图，是我自己总结的队列知识体系。你看一遍，应该就能把整个章节串起来。

这张图把队列的两种存储方式、各自的问题、以及解决方案都串起来了。你顺着箭头看，就能理解整个知识脉络。

6.6 总结

队列这东西，看着简单，用起来坑不少。我总结几个要点：

• 顺序队列：实现简单，但要注意假溢出。用循环队列解决。
• 循环队列：判空判满要小心。我习惯用牺牲一个单元的方法，简单可靠。
• 链式队列：灵活，但注意内存管理。嵌入式系统里慎用。
• 舞伴配对：队列的典型应用，理解了这个，其他类似场景都能举一反三。

---

公众号：蓝海资料掘金营，微信 deep3321