21、动态队列：用动态数组实现循环队列、入队与出队操作

队列这东西，说白了就是「先来后到」。你想想看，食堂打饭、打印机排队、网络数据包处理，哪个不是先进先出？在C语言里实现队列，我个人的习惯是优先用动态数组做循环队列。为什么？因为静态数组太死板，链表又太重，动态数组加循环逻辑，刚好卡在中间——既灵活又高效。

队列的核心思想

队列只有两个正经操作：入队（从尾巴塞数据）和出队（从脑袋取数据）。不允许插队，不允许从中间掏。嗯，这就是纪律。

用数组实现时，你会遇到一个尴尬的问题：出队后，前面的位置就空出来了。如果一直往后加，数组很快就用完了，但前面明明还有空位。怎么办？循环队列就是答案——把数组头尾连起来，形成一个环。

数据结构设计

我习惯这样定义循环队列的结构体：

typedef struct {
    int *data;      // 动态数组指针
    int capacity;   // 数组总容量
    int front;      // 队头下标
    int rear;       // 队尾下标
    int size;       // 当前元素个数
} CircularQueue;

这里有个小细节：front指向队头元素，rear指向队尾元素的下一个位置。为什么要多留一个空位？这是为了区分「队列空」和「队列满」的状态。如果front == rear，队列为空；如果(rear + 1) % capacity == front，队列为满。

初始化与销毁

既然是动态数组，内存就得我们自己管。初始化时分配空间，销毁时释放空间，这是铁律。

CircularQueue* createQueue(int capacity) {
    CircularQueue *q = (CircularQueue*)malloc(sizeof(CircularQueue));
    q->data = (int*)malloc(sizeof(int) * (capacity + 1)); // 多留一个位置
    q->capacity = capacity + 1;
    q->front = 0;
    q->rear = 0;
    q->size = 0;
    return q;
}

void destroyQueue(CircularQueue *q) {
    if (q) {
        free(q->data);
        free(q);
    }
}

注意这里capacity + 1的用意。我故意多分配了一个元素的空间，这样rear永远指向一个空位，方便判断队满。你想想看，如果不留这个空位，front == rear就没办法区分空和满了。

入队操作

入队就是把数据放到rear位置，然后rear往后挪一步。如果到了数组末尾，就绕回开头。

int enqueue(CircularQueue *q, int value) {
    if ((q->rear + 1) % q->capacity == q->front) {
        printf("队列已满，无法入队\n");
        return -1;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
    return 0;
}

这里(q->rear + 1) % q->capacity就是循环的精髓。取模运算让下标在0到capacity-1之间循环。我曾经在嵌入式项目里用这个逻辑做串口数据缓冲，跑了几百万次都没出过问题。

出队操作

出队就是从front位置取数据，然后front也往后挪。同样要处理循环。

int dequeue(CircularQueue *q, int *value) {
    if (q->front == q->rear) {
        printf("队列为空，无法出队\n");
        return -1;
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return 0;
}

完整示例

把上面这些拼起来，就是一个能用的循环队列了。我写个简单的测试：

int main() {
    CircularQueue *q = createQueue(5);
    
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    
    int val;
    dequeue(q, &val);
    printf("出队: %d\n", val);  // 10
    
    enqueue(q, 40);
    enqueue(q, 50);
    enqueue(q, 60);  // 这里会触发队满吗？不会，因为前面出队了一个
    
    while (dequeue(q, &val) == 0) {
        printf("出队: %d\n", val);
    }
    
    destroyQueue(q);
    return 0;
}

运行结果：

出队: 10
出队: 20
出队: 30
出队: 40
出队: 50

看到了吗？虽然我们只创建了容量为5的队列，但通过循环利用，实际上可以连续入队出队很多次。这就是循环队列的魅力。

核心逻辑流程图

下面这张图展示了循环队列的入队和出队流程，以及循环下标的变化：

性能分析

循环队列的入队和出队操作，时间复杂度都是O(1)。这一点比链表实现的队列还要好——链表虽然也是O(1)，但每次操作都要分配或释放节点，有额外开销。

操作	时间复杂度	空间复杂度	说明
入队	O(1)	O(1)	直接赋值，下标循环
出队	O(1)	O(1)	直接取值，下标循环
判空	O(1)	O(1)	比较 front 和 rear
判满	O(1)	O(1)	比较 (rear+1)%cap 和 front

避坑指南

• 我曾经在嵌入式项目里用循环队列做串口接收缓冲，结果忘了处理front和rear的循环，数据一多就数组越界。从那以后，我每次更新下标都会用取模运算，绝不偷懒。
• 注意：动态数组的容量是固定的，如果入队速度大于出队速度，队列迟早会满。实际项目中要监控队列使用率，必要时报警或扩容。
• 还有一点：多线程环境下，入队和出队操作需要加锁。我一般用互斥锁保护front、rear和size的读写，否则会出现数据竞争。

好了，循环队列就讲到这里。动态数组加循环逻辑，这个组合在C语言里非常实用。你可以在自己的项目里试试，比如用它做任务队列、数据缓冲或者消息管道。嗯，动手写一遍，比看十遍都管用。