队列：先进先出的艺术

队列这东西，说白了就是「先来后到」。你想想看，生活中排队买奶茶、食堂打饭，哪个不是先排的先服务？计算机里的队列，本质上就是这种逻辑的抽象。

我个人习惯把队列想象成一根水管——数据从一头进去，从另一头出来。这种结构在操作系统、网络通信、任务调度里随处可见。今天我们就把它彻底搞明白。

队列的定义与核心操作

队列（Queue）是一种操作受限的线性表。限制在哪？只允许在一端插入（队尾），在另一端删除（队头）。这就是所谓的 FIFO（First In First Out）。

核心操作其实就这几个：

• 入队（Enqueue）：在队尾添加一个元素
• 出队（Dequeue）：移除队头元素并返回
• 判空（IsEmpty）：检查队列里有没有元素
• 取队头（Front）：看一眼队头是谁，但不移除
• 取长度（Size）：当前队列有多少元素

嗯，这里要注意：有些教材把 Front 和 Dequeue 合并成一个操作，但实际工程中我建议分开。为什么？因为有时候你只想看看队头数据，并不想把它删掉。

顺序存储：循环队列

用数组实现队列，最直接的想法就是两个指针——front 指向队头，rear 指向队尾的下一个位置。但有个坑：假溢出。

什么意思？你想想看，数组是固定大小的。如果 front 一直往后移，前面空出来的位置就浪费了。rear 到了数组末尾，明明前面还有空位，却没法再入队了。

解决办法？循环队列。把数组当成一个环，rear 走到头了，就绕回开头。

注意判满条件。我刚开始学的时候总想不通：为什么 rear+1 等于 front 就算满了？因为要空出一个位置来区分「空」和「满」的状态。如果 rear 和 front 指向同一个位置，到底是空还是满？说不清楚。所以牺牲一个元素空间，用这个约定来区分。

#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;
}

链式存储：链表实现队列

顺序队列有个硬伤——大小固定。你想想看，如果数据量不确定，用数组要么浪费空间，要么不够用。这时候链式存储就派上用场了。

链式队列其实就是一个单链表，加两个指针：front 指向头结点，rear 指向尾结点。入队就是在尾部插入，出队就是在头部删除。

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;  // 队头指针
    Node *rear;   // 队尾指针
} LinkedQueue;

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

// 入队
void enqueue(LinkedQueue *q, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    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;  // 空队列
    
    Node *temp = q->front;
    *value = temp->data;
    q->front = temp->next;
    
    // 如果出队后队列变空，rear 也要置空
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    return 0;
}

队列的应用：层次遍历与缓冲区

队列在工程里用得非常多。我挑两个最典型的场景说说。

层次遍历（BFS）

二叉树的层次遍历，说白了就是一层一层地扫过去。怎么实现？用队列。

思路很简单：先把根节点入队。然后循环：出队一个节点，访问它，再把它的左右子节点依次入队。直到队列为空。

void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    while (!isEmpty(&q)) {
        TreeNode *node = dequeue(&q);
        printf("%d ", node->data);
        
        if (node->left) enqueue(&q, node->left);
        if (node->right) enqueue(&q, node->right);
    }
}

你看，代码就这么几行。但背后的思想很强大——队列保证了访问顺序是按层来的。先入队的节点先被访问，正好符合层次遍历的要求。

缓冲区（Buffer）

说到缓冲区，我在做网络协议栈的时候深有体会。数据包到达的速度和处理的速度往往不一致，这时候就需要一个队列来缓冲。

生产者-消费者模型就是典型例子。生产者把数据包入队，消费者从队列里取出处理。队列在这里起到了解耦和削峰填谷的作用。

知识体系总览

下面这张图把队列的核心知识点串起来了，你可以对照着复习：

总结一下

队列这东西，核心就三点：

• FIFO 特性：先入先出，这是它的灵魂
• 两种实现：顺序（循环队列）适合大小已知的场景，链式适合动态数据
• 应用广泛：从 BFS 到缓冲区，从打印机任务队列到消息中间件，到处都有它的身影

我个人建议，初学者先把循环队列的代码手写三遍，把边界条件（空、满、一个元素）都跑一遍。等你闭着眼睛都能写对的时候，队列这块就算真正掌握了。

---