第6章队列

课程目录第6章队列

队列：先进先出的艺术

队列这东西，说白了就是「先来后到」。你想想看，生活中排队买奶茶，第一个排队的先拿到，最后一个排队的最后拿到——这就是队列最朴素的思想。我在嵌入式项目里，队列几乎是天天打交道的结构，从串口数据缓冲到任务调度，到处都有它的影子。

队列的定义与特性

队列是一种先进先出（FIFO, First In First Out）的线性表。它只允许在一端插入（称为队尾），在另一端删除（称为队头）。

嗯，这里要注意几个核心操作：

入队（Enqueue）：在队尾添加一个元素
出队（Dequeue）：从队头移除一个元素
队空（Empty）：队列中没有任何元素
队满（Full）：队列已无法再容纳新元素（针对顺序队列）

核心特性：队列只允许在两端操作，中间的元素不能直接访问。这一点和栈完全不同——栈是「后进先出」，队列是「先进先出」。

我个人习惯把队列想象成一根水管：水从一头流进去，从另一头流出来。先流进去的水，一定先流出来。这个比喻在理解循环队列时特别有用。

顺序队列与循环队列

顺序队列就是用数组实现的队列。听起来简单，但有个大坑——假溢出。

什么是假溢出？我举个例子：你有一个长度为5的数组，先入队3个元素，再出队2个。这时候队头指针指向下标2，队尾指针指向下标3。你还能继续入队吗？从数组空间看，下标0和1是空的，但队尾指针已经到末尾了，无法再插入新元素。这就是假溢出——明明有空间，却用不了。

怎么解决？循环队列闪亮登场。

循环队列把数组首尾相连，形成一个环。队尾指针到达数组末尾后，如果数组头部还有空位，就绕回到头部继续插入。这样一来，数组空间就能被充分利用。

我的经验：判断循环队列是空还是满，有两种常用方法：一是牺牲一个存储单元，让队尾指针+1等于队头指针时表示队满；二是额外加一个size变量记录元素个数。我个人偏爱第二种，代码写起来更直观，不容易出错。

来看一个循环队列的C语言实现：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
    int size;   // 当前元素个数
} CircularQueue;

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

// 判断队空
int isEmpty(CircularQueue *q) {
    return q->size == 0;
}

// 判断队满
int isFull(CircularQueue *q) {
    return q->size == MAX_SIZE;
}

// 入队
int enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        return -1;  // 队满，入队失败
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->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;
    q->size--;
    return 0;
}

注意看(q->rear + 1) % MAX_SIZE这行——取模运算就是实现「循环」的关键。当rear到达MAX_SIZE-1时，加1再取模就回到了0，完美绕圈。

我曾经踩过的坑：在嵌入式项目中，我一开始用顺序队列做串口接收缓冲，结果数据一多就出现假溢出，导致丢包。后来换成循环队列，问题立刻解决。所以，如果你在资源受限的环境下做队列，循环队列几乎是唯一的选择。

链式队列的实现

链式队列就是用链表实现的队列。它没有固定大小限制，理论上可以无限扩展（只要内存够）。

链式队列的结构很简单：一个头指针指向队头节点，一个尾指针指向队尾节点。入队时在尾部插入新节点，出队时删除头部节点。

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;
    if (q->front == NULL) {
        q->rear = NULL;  // 队列变空
    }
    free(temp);
    return 0;
}

链式队列的好处是动态扩展，不会出现队满的情况。但代价是每个节点需要额外的指针空间，而且频繁的malloc/free在实时性要求高的场景下可能成为瓶颈。

我建议：在内存充足、数据量不确定的场景用链式队列；在资源受限、数据量可预估的场景用循环队列。比如在单片机里，我几乎只用循环队列——malloc太不可控了。

队列的应用：广度优先搜索

队列最经典的应用之一就是广度优先搜索（BFS）。BFS的核心思想是：从起点出发，先访问所有距离为1的节点，再访问所有距离为2的节点，以此类推。这种「层层推进」的方式，天然适合用队列来实现。

BFS的算法流程：

将起始节点入队
标记起始节点为已访问
当队列不为空时，循环执行：

出队一个节点
访问该节点的所有未访问的邻接节点
将这些邻接节点入队并标记为已访问

来看一个简单的BFS示例，用队列遍历图：

#define MAX_NODES 100

// 邻接矩阵表示的图
typedef struct {
    int edges[MAX_NODES][MAX_NODES];
    int numNodes;
} Graph;

void bfs(Graph *g, int start) {
    int visited[MAX_NODES] = {0};
    CircularQueue q;
    initQueue(&q);
    
    visited[start] = 1;
    enqueue(&q, start);
    
    while (!isEmpty(&q)) {
        int node;
        dequeue(&q, &node);
        printf("访问节点: %d\n", node);
        
        // 遍历所有邻接节点
        for (int i = 0; i < g->numNodes; i++) {
            if (g->edges[node][i] && !visited[i]) {
                visited[i] = 1;
                enqueue(&q, i);
            }
        }
    }
}

BFS的应用场景非常多：

最短路径：在无权图中，BFS找到的路径就是最短路径
迷宫求解：从起点到终点的最短路径
网络爬虫：从起始页面开始，逐层抓取链接
社交网络：查找两个人之间的最短关系链

避坑指南：BFS一定要记得标记已访问节点，否则会陷入死循环。我曾经在写迷宫求解时忘了这茬，结果程序跑起来就停不下来——队列里反复入队同一个节点，无限循环。嗯，从那以后我写BFS第一件事就是检查visited数组。

下面这张图展示了队列在BFS中的核心作用：

从图中可以看到，BFS的每一步都是从队头取出一个节点，然后将其未访问的邻接节点从队尾入队。这种「先进先出」的特性，保证了节点按照距离起点的远近依次被访问——距离为1的先入队，自然先出队被访问；距离为2的后入队，后出队被访问。

队列虽然结构简单，但它在算法和系统设计中的地位举足轻重。从操作系统的任务调度，到网络协议的数据包缓冲，再到图算法中的BFS，队列无处不在。掌握好队列，你的编程工具箱里就多了一把利器。

📚 课程目录

队列：先进先出的艺术

队列的定义与特性

顺序队列与循环队列

链式队列的实现

队列的应用：广度优先搜索