C++队列全解析：从循环队列到阻塞队列与线程池

队列（queue）大概是我学 C++ 数据结构时第一个真正觉得“这玩意能干实事”的东西。不是因为 FIFO 这三个字母看起来规范，而是当你用一支队列做完带缓冲的任务处理、滑动窗口统计、BFS 寻路之后，你会很直观地感受到：先进先出这种秩序本身就是一种生产力。这篇基础学习记录不照顾任何平台，就是用 C++ 把队列从数组到循环、从链表到 STL、最后再到阻塞队列和线程池这块掰开聊一遍，适合正在学数据结构的同学，也适合想系统确认自己有没有漏掉细节的选手。

1. 从“排队打饭”理解队列：C++里的基本盘

1.1 队列的核心本质：先进先出

要理解队列，最偷懒的办法是直接想象食堂排队。先到的人先打饭，后到的人站后面，谁也别抢，这就叫 FIFO（First In First Out，先进先出）。计算机里有大量问题天然带着这种“先后次序”：打印任务按提交顺序输出、网络请求按到达顺序处理、服务器上的 IO 请求排队等待磁盘响应。如果不维护这种次序，系统很快就乱了。

队列对外暴露的操作其实比链表、树这些简单得多，通常就五个核心动作：

• push / enqueue：往队尾放一个元素。
• pop / dequeue：从队头拿走一个元素。
• front：看一眼队头元素是谁，但是不拿走。
• back：看一眼队尾元素是谁，队尾一般只读不操作。
• empty / size：判断队列是否为空、当前有多少元素。

和栈对比一下更清楚：栈是一摞盘子，后放的先取；队列是一排人，先站的先走。栈叫 LIFO（Last In First Out），队列叫 FIFO。很多同学会在写算法题的时候把这两个搞混，我建议你直接记住一句话——凡是需要“按到达先后顺序逐个处理”的场景，优先想到队列。

1.2 用数组先写一版能跑的队列

先不急着上 STL 的 std::queue，否则基础不稳。用 C++ 手写一个最简单的固定大小队列，可以帮助你搞清楚队头和队尾到底是怎么回事。

cpp复制#include <iostream>
const int MAXN = 100;

struct ArrayQueue {
    int data[MAXN];
    int head = 0;  // 队头位置
    int tail = 0;  // 下一个空闲位置
};

void push(ArrayQueue& q, int x) {
    q.data[q.tail++] = x;  // 注意：这个写法很快会暴露问题
}

int front(const ArrayQueue& q) {
    return q.data[q.head];
}

void pop(ArrayQueue& q) {
    ++q.head;
}

int main() {
    ArrayQueue q;
    push(q, 10);
    push(q, 20);
    pop(q);
    std::cout << front(q) << std::endl;  // 20
    return 0;
}

这个版本能跑，但你马上会撞到两个问题。第一，tail 会一直往上加，数组一旦越界程序就崩；第二，head 前面的空间其实已经空了，但数组尾部已经满了，这在数据结构里有个专门的称呼叫“假溢出”。所以实际工程里几乎没人直接用这种最朴素的数组写法，我们需要给它做两个升级方向：让数组空间循环复用，或者把存储换成链表。

2. 三种经典实现：普通数组、循环队列、链式队列

2.1 普通数组队列的死穴：假溢出

假设数组长度为 5，你的操作序列是：进 1、进 2、进 3，然后出 1、出 2。此时 head 指向 2，tail 指向 3，数组里还有 2 个元素。你再想进一个 4，tail 变成 4，再进一个 5，tail 变成 5，越界了。

但是看数组下标 0 和 1，它们早就是空闲状态了。这个“明明有空间却用不上”的问题就叫假溢出。很多新手上来一脸懵：明明数组还有位置，凭什么报错？答案是你的指针设计没有回收前面让出来的空间，数组是线性铺开用的，不是环形复用。

解决假溢出的第一思路是把数组头尾相接，想象成一条环形跑道。这就是循环队列，也是算法题目和嵌入式程序里最常见的队列实现方式。

2.2 循环队列：数组空间的“贪吃蛇”

循环队列的核心思想：当 tail 走到数组末尾时，不是越界，而是通过取模运算跳回下标 0。我在学习的时候，最喜欢用的一种循环队列参数是 rear（队尾位置）和 length（当前元素个数），这也是你搜到的那个经典题目描述里提到的方案。

cpp复制template<typename T, size_t M>
class CircularQueue {
private:
    T data[M];
    size_t rear = 0;      // 新元素应写入的位置
    size_t length = 0;    // 队列当前元素个数
public:
    bool enqueue(const T& val) {
        if (length == M) return false;   // 队列满
        data[rear] = val;
        rear = (rear + 1) % M;           // 绕回
        ++length;
        return true;
    }

    bool dequeue(T& out) {
        if (length == 0) return false;   // 队列空
        size_t front = (rear - length + M) % M;  // 关键公式
        out = data[front];
        --length;
        return true;
    }

    T front() const {
        return data[(rear - length + M) % M];
    }

    bool empty() const { return length == 0; }
};

这里有个细节值得重点说一下：front 怎么算？因为数组是环形跑的，队头的位置并不是一个直接记录的变量，而是由队尾和长度反推。(rear - length + M) % M 这个式子里，为什么要加一个 M？因为 rear - length 可能变成负数，而 C++ 的 size_t 是无符号整数，一旦下溢会变成一个极大值，取模结果就全错了。加上 M 再取模，本质就是把负数搬回到正数范围内，这是大多数教科书不会专门标出来的坑。

另一种常见的循环队列写法是记录 front 和 rear 两个指针，为了让“队空”和“队满”能区分开，会强制牺牲一个数组位置：当 (rear + 1) % M == front 时认定队满。两种方案都能用，但我个人更推荐 rear + length 方案，因为判空判满的条件直接清晰，不用纠结空和满到底差在哪里。

以 rear 和 length 为核心的循环队列，所有操作的时间复杂度都是 O(1)。队满时进不去了，队空时出不来了，边界条件清清楚楚。在内存受限的嵌入式环境里，这种实现非常常见，比如串口接收缓冲区、音频帧的环形缓冲，本质上都是同一个东西。

2.3 链式队列：动态扩容不浪费

如果队列的元素数量波动很大，刚开数组开小了不够用，开大了又浪费，那就轮到链表出场。链式队列的思路是队尾入队、队头出队，每次动态申请节点，队列长度只受内存限制。

cpp复制struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

class LinkedQueue {
private:
    ListNode* head;  // 哨兵节点，head->next 才是队头
    ListNode* tail;  // 队尾
    int size_;
public:
    LinkedQueue() : head(new ListNode(0)), tail(head), size_(0) {}

    ~LinkedQueue() {
        while (head) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
    }

    void push(int x) {
        tail->next = new ListNode(x);
        tail = tail->next;
        ++size_;
    }

    bool pop() {
        if (size_ == 0) return false;
        ListNode* del = head->next;
        head->next = del->next;
        if (tail == del) tail = head;   // 删掉了最后一个元素，重置 tail
        delete del;
        --size_;
        return true;
    }

    int front() const {
        return head->next->val;
    }

    int size() const { return size_; }
};

这里有一个容易翻车的细节：我用了哨兵节点 head，好处是队头和队尾的边界处理统一，队列为空时 head->next == nullptr，不用单独判断 head == nullptr。删除最后一个元素的时候，tail 还指着被删除的节点，必须把 tail 重置回 head，否则下一次 push 会通过一个悬空指针写内存，直接崩溃。这个 bug 我最初实战时就踩过一次，调试了半天才定位到。

链式队列的 push 和 pop 都是 O(1)，但不代表它完美：每个节点多花一个 next 指针的内存，频繁 new/delete 还会产生内存碎片。所以链式队列一般用在“容量不可预知”的场景，比如任务队列、事件队列；而如果容量上限固定，循环队列往往更香。

2.4 三种实现选型对照

把三种实现放一起看，选型逻辑会变得非常清楚：

如果你是准备面试，我建议至少能手写循环队列的 rear + length 版和链式队列的“哨兵节点 + tail”版。这两个版本边界条件最干净，写起来也不容易漏。

3. 直接上 STL：queue、deque 与双端队列实战

3.1 queue 的正确打开方式

写工程代码时，在 C++ 里直接用 std::queue 最省事。它属于容器适配器，底层默认帮你包了一个 std::deque，你只需要关心队列语义。基本用法是这样：

cpp复制#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << "front=" << q.front() << std::endl;  // 1
    std::cout << "back=" << q.back() << std::endl;   // 3

    q.pop();
    std::cout << "front=" << q.front() << std::endl;  // 2
    std::cout << "size=" << q.size() << std::endl;    // 2
    return 0;
}

一个新手容易搞错的地方是：pop() 没有返回值，它只是把队头元素删掉。你要是想拿队头，必须先用 front() 取值，再 pop()。直接执行 int x = q.pop(); 编译都过不了。

还有一个容易被忽略的知识点：std::queue 不提供迭代器，不能遍历。这是设计故意的——它是一层约束性包装，只暴露队列语义，不让你把人家的底层逻辑搅混。如果你真的有遍历、按下标访问的需求，说明你不该用 queue，应该用 deque 或者 vector。std::queue 的底层容器还可以显式换成 std::list，写法是 std::queue<int, std::list<int>>，只不过不是特殊情况很少有人这么干。

3.2 deque 比 queue 多出什么

std::deque（双端队列）就是在队头和队尾都可以 O(1) 插入删除的容器。你可以把它理解成 queue 的“完全体”：

cpp复制#include <deque>

std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_back();
dq.pop_front();
std::cout << dq.front() << " " << dq.back() << std::endl;

deque 的底层实现很有意思，它不是一个连续的数组，而是一段段固定大小的缓冲区，通过一个中控映射表把它们串起来。所以它既能做到两端快速插入删除，又能支持下标访问（虽然中间隔了一层映射，常数比 vector 大一点，但仍是 O(1) 级别）。

实际开发里我更多是拿 std::deque 做滑动窗口、单调队列、撤销记录这类需要两端操作的数据结构。刷题时写的 vector<int> window 往往需要手动维护头部下标，写起来很别扭；换成 deque 之后，pop_front 和 push_back 直接天然配对，逻辑清楚很多。

3.3 单调队列：用 deque 做滑动窗口最大值

单调队列是队列知识里一个非常经典的进阶应用，典型题目就是滑动窗口最大值。给你一个数组 nums 和一个窗口大小 k，窗口从左往右每次滑一格，要你输出每个窗口里的最大值。暴力做法是每个窗口都扫一遍，复杂度 O(n*k)，数据一大就超时。

单调队列的优化点在于：窗口中已经确定不可能是最大值的元素，没必要等它滑出窗口再处理，立刻踢掉就行。 我用一个双端队列存数组下标，并让这些下标对应的值保持从队头到队尾单调递减，那么队头永远就是当前窗口的最大值。

cpp复制std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::deque<int> q;              // 存数组下标
    std::vector<int> ans;
    for (int i = 0; i < (int)nums.size(); ++i) {
        // 队尾元素比当前值小或相等，它永远不可能成为窗口最大值，出队
        while (!q.empty() && nums[q.back()] <= nums[i]) {
            q.pop_back();
        }
        q.push_back(i);

        // 队头如果已经滑出窗口，出队
        if (q.front() <= i - k) {
            q.pop_front();
        }

        // 窗口长度达到 k 之后，开始记录答案
        if (i >= k - 1) {
            ans.push_back(nums[q.front()]);
        }
    }
    return ans;
}

这个代码里有一个值得细品的设计：为什么存下标而不是存值？因为单靠值，你没法判断它是否还在窗口内。存下标之后，每次滑动可以用 q.front() <= i - k 精确判断过期元素。每个元素最多入队一次、出队一次，整体 O(n)，非常优雅。想求滑动窗口最小值的话，对称地把单调递减改成单调递增即可，其他逻辑一字不改。

4. 工程晋级：阻塞队列、线程池与无锁队列

4.1 裸 queue 在多线程下为什么不安全

把 std::queue 直接丢给多线程用，等于在悬崖边跳舞。push 和 pop 不是原子操作，empty() 和 pop() 之间的状态也可能瞬间变化。举一个典型场景：线程 A 判断队列非空，准备出队；线程 B 在同一时刻把最后一个元素出队了；线程 A 继续执行，队列已经空了，它取到了一个还没被初始化的对象，甚至直接对空队列调用 front()，崩溃。

更隐蔽的情况是容器的内部操作被打断：STL 容器的修改涉及到指针或内存布局的变化，两个线程同时 push 可能互相覆盖内部状态，轻则数据错乱，重则内存泄漏。所以要明确一个结论：多线程环境下不能直接用裸 queue，要么加锁保护，要么用专门设计为线程安全的容器/队列实现。

4.2 手写一个阻塞队列：mutex + condition_variable

阻塞队列是生产者和消费者模型最常用的基础设施。所谓阻塞，是指队列满时生产者 push 会等待，队列空时消费者 pop 会等待。C++ 标准库没有直接提供现成的阻塞队列类，但用 mutex 和 condition_variable 组合手写一个成本很低。

cpp复制#include <deque>
#include <mutex>
#include <condition_variable>

template<typename T>
class BlockingQueue {
private:
    std::deque<T> q;
    std::mutex mtx;
    std::condition_variable not_empty;
    std::condition_variable not_full;
    size_t capacity;

public:
    explicit BlockingQueue(size_t cap) : capacity(cap) {}

    void push(const T& val) {
        std::unique_lock<std::mutex> lock(mtx);
        // 必须用 while 而非 if，防止伪唤醒
        not_full.wait(lock, [&]() { return q.size() < capacity; });
        q.push_back(val);
        not_empty.notify_one();
    }

    T pop() {
        std::unique_lock<std::mutex> lock(mtx);
        not_empty.wait(lock, [&]() { return !q.empty(); });
        T val = std::move(q.front());
        q.pop_front();
        not_full.notify_one();
        return val;
    }
};

这里有两个必须强调的细节。第一是条件变量的等待条件要写在 while 或者 wait 函数的第二个参数里，不要用 if。因为 wait 存在伪唤醒（spurious wakeup）的可能，如果只判断一次，即使条件仍然不满足，代码也会继续往下走。第二，wait 内部会释放 mtx 锁并挂起线程，被 notify 唤醒后会自动重新上锁，这就保证了队列操作的原子性，不需要你手动加二次锁。

阻塞队列在 C++ 工程里的出场率极高，比如线程池的任务队列、网络服务器接收连接后的请求缓冲。它的“背压”特性非常有用：任务突然暴增时，push 线程被阻塞住，不会无限堆积，这样内存和下游系统不会直接被冲垮。

4.3 线程池的阻塞队列怎么选：有界 vs 无界

在线程池实现里，任务队列选用有界还是无界，设计意图完全不同。无界队列实现简单，任务永远能入队，不会因为队列满而拒绝；但代价是任务数量不可控时内存会持续上涨，很可能 OOM 或者把系统资源耗尽。有界队列则相反，队列一旦满了生产者必须等待或放弃，等于把压力反馈给上游，让整个系统自然限流。

从我实际项目经验看，做多线程任务调度时我更倾向于有界队列配合拒绝策略：队列满之后，要么阻塞，要么记录日志并丢弃非核心任务。这样系统最差的情况也是“任务堆积到阈值后开始丢弃”，而不会直接挂掉。无界队列虽然用起来一时爽，但线上排查问题的时候，你基本无法判断任务量到底涨到了什么级别。

在经典框架里，有界/无界的区别也有对应物：Java 的 LinkedBlockingQueue 默认无界，ArrayBlockingQueue 强制有界；C++ 这边标准库没有内置，我会直接封装一个上面写的 BlockingQueue，并把 capacity 通过构造函数固定下来。

4.4 无锁队列与 CAS、ABA 问题

无锁队列这几年在各种“高性能”项目里很火，核心思想是用原子操作（CAS）替代互斥锁，避免线程被挂起和唤醒的开销。最典型的是单生产者单消费者（SPSC）的有界环形队列：用两个 std::atomic<size_t> 分别记录读位置和写位置，配合内存序控制就可以做到无锁。

cpp复制#include <atomic>
#include <array>

template<typename T, size_t N>
class SPSCQueue {
private:
    std::array<T, N> buffer{};
    std::atomic<size_t> head{0};   // 消费者读位置
    std::atomic<size_t> tail{0};   // 生产者写位置

public:
    bool push(const T& val) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t h = head.load(std::memory_order_acquire);
        if ((t + 1) % N == h) return false;  // 队列满
        buffer[t] = val;
        tail.store((t + 1) % N, std::memory_order_release);
        return true;
    }

    bool pop(T& out) {
        size_t h = head.load(std::memory_order_relaxed);
        size_t t = tail.load(std::memory_order_acquire);
        if (h == t) return false;  // 队列空
        out = buffer[h];
        head.store((h + 1) % N, std::memory_order_release);
        return true;
    }
};

这段代码只适用于单生产者单消费者，千万别直接拿去当 MPMC（多生产者多消费者）队列用。多线程环境下做 MPMC 无锁队列，绕不开 CAS 和 ABA 问题。

CAS 的意思是比较并交换：只有当前值和期望值相等时才把值改成目标值。ABA 问题是——线程 A 读取某个指针值为 X，准备 CAS 时被挂起；线程 B 把值改成 Y 又改回 X；线程 A 恢复后继续 CAS，发现当前值还是 X，于是成功修改，但实际上这个 X 已经不是原来那个 X 了。这在无锁链表中会造成致命错误，甚至导致链表断链。

解决 ABA 的常见办法是给每个指针附带一个版本号，每改一次就递增一次。C++ 实现时可以用一个 uintptr_t 整数，低位存指针高位存计数器，CAS 时同时比较两者。不过说句实在话，工程里 99% 的场景都不需要你去抗无锁队列。互斥锁 + 条件变量在低竞争场景下性能足够，代码简单且不容易出错；无锁队列只有在极致的低延迟、高频交易、核心热路径这类需求下才值得引入，而且引入后必须配严格的并发测试。

5. 队列在算法与消息系统中的进阶延伸

5.1 BFS 广搜的标准姿势

队列在算法里的另一个高光应用是广度优先搜索（BFS）。因为 BFS 天然要求“按层扩展”，先发现的节点必须先处理，这和队列的 FIFO 完全一致。做迷宫最短路径、拓扑排序、多源扩散问题时，BFS 几乎是标配。

cpp复制#include <queue>
#include <vector>
#include <utility>

// 迷宫 BFS：grid[x][y] = 1 为障碍
int bfs(std::vector<std::vector<int>>& grid, int sx, int sy, int tx, int ty) {
    int row = grid.size(), col = grid[0].size();
    std::vector<std::vector<int>> dist(row, std::vector<int>(col, -1));
    std::queue<std::pair<int, int>> q;

    q.push({sx, sy});
    dist[sx][sy] = 0;

    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == tx && y == ty) return dist[x][y];

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;  // 不可达
}

这个模板值得背下来：入队时标记访问状态，不要在出队时才标记，否则同一个节点可能被多个邻居重复入队，复杂度直接爆炸。这也是很多刚学 BFS 的人最容易写错的地方。

5.2 消息队列与“重复消费”问题

很多初学者会把数据结构里的队列和分布式消息队列混在一起。数据结构里的队列是在内存里排队，消息队列（比如 Kafka、RabbitMQ、RocketMQ 这些）则是把消息发到中间件，供多个消费者处理，它们只有“生产者、消费者模型”这一点是相通的。

重复消费是消息队列领域最经典的问题。原因是很多消息系统默认采用“至少一次”的投递语义，消费者处理完消息之后可能还没来得及提交确认，连接断了，消息就被重新投递一遍。这不是 bug，而是系统为了不丢消息故意的取舍。

应对重复消费，核心思路不是让消息系统只推一次，而是让消费处理具备幂等性。最简单的做法是每个业务消息携带全局唯一 ID，消费者在处理前先查一下去重表（比如数据库唯一键或 Redis set），已经处理过的 ID 直接跳过。另一个做法是把消息写入与查询做成“同一条事务”，保证“写入 + 消费记录”要么同时成功，要么同时失败。金融转账这类业务场景，重复消费对账没做好的后果很严重，幂等设计必须当成一等公民来考虑。

5.3 前缀和、单调栈？先分清队列的边界

在刷题过程中会看到不少带“栈”“队”“前缀”标签的题目，比如前缀和、单调栈、单调队列，三者边界很容易混。前缀和是对数组做预处理，让区间求和变成 O(1)，它和队列无关，它是一维动态规划的一种简化。单调栈和单调队列才是亲兄弟：单调栈适合求“下一个更大/更小元素”，它只在一端操作；单调队列适合滑动窗口类问题，因为它同时保留了窗口的左右边界信息，你需要双端删除过期元素。

判断该用哪个有个简单口诀：只从一端处理就上单调栈，窗口会滑动就需要单调队列。 这层区分搞清楚了，你在刷算法题时少走很多弯路。

6. 实战排坑清单：从编译到运行的常见问题

6.1 环境问题：VSCode 下队列项目跑不起来

队列代码本身很简单，但很多人卡在环境配置上。我用 VSCode 写 C++ 时踩过的坑主要集中在三份配置上：tasks.json 负责编译，launch.json 负责调试，c_cpp_properties.json 负责让智能提示认识头文件。

tasks.json 里最核心的是 args，通常写成这样：

json复制{
    "type": "cppbuild",
    "command": "/usr/bin/g++",
    "args": [
        "-g",
        "-std=c++17",
        "${fileDirname}/*.cpp",
        "-o",
        "${fileDirname}/main"
    ],
    "group": "build"
}

注意编译指令里的 -std=c++17，如果漏掉，std::make_unique、结构化绑定这些特性都用不了。launch.json 里需要确认 miDebuggerPath 指向的 gdb 路径存在，Windows 上如果用的 MinGW，还要检查环境变量 PATH 是否包含了 g++ 目录。最让人头疼的其实是头文件找不到的报错，比如 #include <queue> 提示找不到，十有八九是 c_cpp_properties.json 没配置 includePath，或者编译器选了 Windows 的 cl.exe 而不是 MinGW 的 g++。

6.2 逻辑问题：front、rear 与 length 的边界陷阱

手写循环队列时我见过最多的问题，是把 rear 当成队头来用，出队时错误地取了 data[rear]。记住：rear 永远指向下一个新元素写入的位置，不是队头。 队头要靠 (rear - length + M) % M 反推。我在写循环队列的时候一直提醒自己：length 是核心锚点，只要它维护对了，其他都可以推出来。

另一个容易出 bug 的地方是取模时忘记处理负数。用 size_t 或者 unsigned 类型时，(rear - length) 一旦为负会直接下溢，得到一个大得离谱的值。所以循环队列的取模运算一定要写成 (rear - length + M) % M，手动把负数的可能性消灭掉。

6.3 排查速查表

这篇文章写到这里，我自己最有共鸣的一句话是：队列学得好不好，看的不是你背了多少 API，而是边界条件能否一把写对。 循环队列的取模、链式队列的哨兵节点、阻塞队列的条件变量、无锁队列的内存序，每一个细节背后都是真实的工程教训。把这三层吃透，以后不管是做业务系统里的任务调度，还是刷算法题碰到的 BFS、滑动窗口，你都会比别人少花很多时间在 debug 上。