队列的三大实战应用：BFS、层次遍历与生产者消费者

队列这东西，说白了就是个「先进先出」的容器。但你别小看它，我在嵌入式项目里靠它解决过不少棘手问题。今天咱们就聊聊队列的三个经典应用场景——广度优先搜索、层次遍历二叉树，还有生产者消费者模型。

这三个场景，其实都抓住了队列的核心特性：先来的先处理，后来的排队等。你想想看，是不是这个理？

一、广度优先搜索（BFS）基础

BFS 是什么？我习惯把它理解成「水波扩散」。你往池塘里扔一颗石子，波纹是一圈一圈往外扩的。BFS 也是这样，从起点开始，一层一层往外探索。

为什么 BFS 必须用队列？因为队列能保证「先发现的节点先被处理」。这正好符合 BFS 的层级顺序。

来看个简单的迷宫寻路例子。假设我们有一个 5x5 的网格，从 (0,0) 出发，要找到 (4,4)：

#include <stdio.h>
#include <stdlib.h>

#define ROWS 5
#define COLS 5

// 方向数组：上、下、左、右
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

typedef struct {
    int x, y;
} Point;

typedef struct {
    Point data[100];
    int front, rear;
} Queue;

void bfs(int maze[ROWS][COLS], int startX, int startY) {
    Queue q = { .front = 0, .rear = 0 };
    int visited[ROWS][COLS] = {0};
    
    // 起点入队
    q.data[q.rear++] = (Point){startX, startY};
    visited[startX][startY] = 1;
    
    while (q.front < q.rear) {
        Point cur = q.data[q.front++];
        printf("访问: (%d, %d)\n", cur.x, cur.y);
        
        // 检查四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dirs[i][0];
            int ny = cur.y + dirs[i][1];
            
            if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS
                && !visited[nx][ny] && maze[nx][ny] == 0) {
                visited[nx][ny] = 1;
                q.data[q.rear++] = (Point){nx, ny};
            }
        }
    }
}

BFS 的时间复杂度是 O(V+E)，V 是节点数，E 是边数。空间复杂度最坏情况 O(V)。

二、层次遍历二叉树

层次遍历，其实就是 BFS 在二叉树上的特化版本。每一层从左到右依次访问。

我记得有一次做嵌入式 GUI 的菜单系统，需要按层级展开菜单项。用层次遍历二叉树，一行代码都不用改，直接套用 BFS 模板就搞定了。

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

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

这里有个细节：如果你需要区分每一层，可以在每层结束时插入一个 NULL 标记，或者记录当前层的节点数。

void levelOrderWithLevel(TreeNode *root) {
    if (!root) return;
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    int level = 0;
    while (!isEmpty(&q)) {
        int levelSize = size(&q);  // 当前层的节点数
        printf("第 %d 层: ", level);
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = dequeue(&q);
            printf("%d ", node->val);
            
            if (node->left) enqueue(&q, node->left);
            if (node->right) enqueue(&q, node->right);
        }
        printf("\n");
        level++;
    }
}

三、生产者消费者模型

这个模型在嵌入式系统里太常见了。一个任务产生数据，另一个任务处理数据。中间用队列缓冲。

我曾经在一个数据采集项目里用过这个模式。传感器以 100Hz 的频率产生数据，而处理模块需要 50ms 才能处理完一条。如果没有队列缓冲，数据就会丢失。

typedef struct {
    int buffer[BUFFER_SIZE];
    int front, rear;
    int count;
    pthread_mutex_t mutex;
    pthread_cond_t not_full;
    pthread_cond_t not_empty;
} CircularQueue;

void producer(CircularQueue *q, int item) {
    pthread_mutex_lock(&q->mutex);
    
    while (q->count == BUFFER_SIZE) {
        // 队列满了，等待消费者消费
        pthread_cond_wait(&q->not_full, &q->mutex);
    }
    
    q->buffer[q->rear] = item;
    q->rear = (q->rear + 1) % BUFFER_SIZE;
    q->count++;
    
    pthread_cond_signal(&q->not_empty);
    pthread_mutex_unlock(&q->mutex);
}

int consumer(CircularQueue *q) {
    pthread_mutex_lock(&q->mutex);
    
    while (q->count == 0) {
        // 队列空了，等待生产者生产
        pthread_cond_wait(&q->not_empty, &q->mutex);
    }
    
    int item = q->buffer[q->front];
    q->front = (q->front + 1) % BUFFER_SIZE;
    q->count--;
    
    pthread_cond_signal(&q->not_full);
    pthread_mutex_unlock(&q->mutex);
    
    return item;
}

四、三种应用的核心对比

应用场景	队列角色	关键特性	常见坑点
BFS	待访问节点缓存	保证层级顺序	visited 标记时机
层次遍历	节点访问顺序控制	区分每层边界	空指针检查
生产者消费者	数据缓冲	线程安全、流量控制	虚假唤醒、死锁

这三个场景，本质上都是利用队列的 FIFO 特性来「排队」。BFS 排队的是节点，层次遍历排队的是树节点，生产者消费者排队的是数据。

你想想看，是不是这个道理？队列就是一个「先来后到」的秩序维护者。搞懂了这一点，你就能灵活运用它解决各种实际问题。

嗯，队列的应用就聊到这儿。这三种模式你掌握了，大部分需要「排队」的场景你都能应对。代码写多了你会发现，很多复杂问题拆解到最后，就是队列、栈这些基础数据结构的组合运用。

---

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