Chapter 23: Queue

std::queue 解决的是“只允许从一端写入、另一端读取”的顺序约束问题。调用者把元素放到队尾，再从队首取出元素，最早进入队列的元素最早离开队列。这种约束让任务排队、广度优先搜索、事件缓冲和生产消费模型可以直接表达“到达顺序就是处理顺序”。

本章讨论的对象是标准库容器适配器 std::queue。它定义在头文件 <queue>，标准形式可以写成 std::queue<T, Container>，默认底层容器是 std::deque<T>。C++ 工作草案对 queue 的定义显示，底层容器需要支持 front()、back()、push_back() 和 pop_front()；cppreference 对 std::queue 的描述也说明它把元素压入底层容器尾部，并从底层容器头部弹出。相关标准草案入口见 C++ working draft queue definition，接口摘要可见 cppreference: std::queue。

读完本章后，读者应能把一次 queue 操作追踪成底层容器的端点操作，判断某个底层容器能否作为 queue 的 Container，解释 front()、back()、push()、pop() 对对象状态的影响，并在工程场景中区分 std::queue 的顺序语义、容量边界和同步边界。

本章贯穿使用下面这个任务队列例子。它足够短，可以展示 FIFO 顺序、端点读取和 pop() 的对象销毁路径。

#include <queue>
#include <string>

struct Job {
    int id;
    std::string payload;
};

void run(Job job);

void drain_jobs(std::queue<Job>& jobs) {
    while (!jobs.empty()) {
        Job current = std::move(jobs.front());
        jobs.pop();
        run(std::move(current));
    }
}

这段代码的关键点在两行：jobs.front() 访问队首元素，jobs.pop() 删除同一个队首元素。std::queue 的 pop() 返回 void，因此读取和删除天然分成两个动作。对 move-only 或代价较高的元素，常见写法是先从 front() 移出对象，再调用 pop() 结束队首元素的生命周期。

23.1 FIFO 语义与容器适配器目标

FIFO 是 first-in, first-out 的缩写，表示先进入队列的元素先离开队列。在 std::queue 中，写入端点是 back，读取和删除端点是 front。这个端点分工让队列只表达“等待处理的线性顺序”，调用者无需关心底层容器内部是分段数组、链表，还是其他满足接口要求的序列容器。

容器适配器（container adaptor）是一类用底层容器保存元素、再向外暴露受限接口的标准库类型。std::queue 的目标是把底层容器的多种能力收窄成 FIFO 能力。底层 std::deque 原本可以从前后两端插入、删除，也可以迭代访问；套上 std::queue 之后，调用者只得到 push()、pop()、front()、back()、empty()、size() 等队列操作。

把适配器看成“接口收窄层”比把它看成新容器更准确。常见实现形状可以简化成下面这样：

template<class T, class Container = std::deque<T>>
class queue_like {
protected:
    Container c;

public:
    bool empty() const { return c.empty(); }
    std::size_t size() const { return c.size(); }

    T& front() { return c.front(); }
    T& back() { return c.back(); }

    void push(const T& value) { c.push_back(value); }
    void push(T&& value) { c.push_back(std::move(value)); }
    void pop() { c.pop_front(); }
};

这段代码是教学简化版，用来说明接口转发关系。真实标准库实现还会处理模板参数、allocator、异常规格、比较运算、构造函数和版本演进。核心路径保持稳定：push() 转到底层 push_back()，pop() 转到底层 pop_front()，front() 和 back() 直接读取底层容器两端。

贯穿例子中的 jobs 保存了若干 Job 对象。假设依次执行 push(Job{1, "parse"})、push(Job{2, "index"})、push(Job{3, "flush"})，队列状态可以理解为 front 指向 id == 1 的任务，back 指向 id == 3 的任务。第一次循环读取 front() 得到任务 1，随后 pop() 删除任务 1；第二次循环读取任务 2。队列顺序只由进入顺序决定，Job::id 的数值和 payload 内容参与业务逻辑，但它们不参与队列内部排序。

下面这张图只描述 std::queue 的端点路径，省略底层容器的内存布局。

图中的关键关系是 push 总是改变队尾，front 只读取队首，pop 删除队首。只要调用者通过 std::queue 的公开接口操作，就无法从中间插入元素，也无法跳过队首直接删除后面的元素。这就是适配器保护 FIFO 语义的方式。

std::queue 的复杂度承诺来自底层容器。默认 std::deque 支持高效的两端操作，所以适合作为默认实现。若底层容器换成 std::list，FIFO 语义仍然成立，但每个元素成为独立节点，内存分配和缓存局部性会发生变化。判断 queue 成本时，先看 queue 接口语义，再看底层容器端点操作成本，最后看元素构造、移动、析构和 allocator 行为。

23.2 默认 deque 与可替换底层容器条件

std::queue<T> 默认展开为 std::queue<T, std::deque<T>>。std::deque 适合做默认底层容器，因为它支持 front()、back()、push_back() 和 pop_front()，并且面向两端增长。对 FIFO 队列来说，最常见的修改路径正好落在这两个端点上。

可替换底层容器需要同时满足两类条件。第一类是类型条件：底层容器的 value_type 必须与 std::queue 的元素类型一致。第二类是操作条件：底层容器需要以通常语义提供 front()、back()、push_back() 和 pop_front()。因此 std::deque<T> 和 std::list<T> 可以作为常见选择；std::vector<T> 有 front()、back() 和 push_back()，但缺少 pop_front()，所以它不是合格的 std::queue 底层容器。

可以用同一组维度比较 deque 和 list 作为底层容器的差异：

底层容器	端点操作	元素布局	iterator / reference 观察点	适合场景
std::deque<T>	支持 push_back() 与 pop_front()	分段连续存储	两端修改的失效规则由 deque 决定	通用任务队列、BFS、事件缓冲
std::list<T>	支持 push_back() 与 pop_front()	每元素独立节点	节点位置较稳定，但每个节点有额外指针和分配成本	元素很大、需要节点稳定性、队列长度变化频繁

这张表给出的是工程判断入口。std::queue 自身隐藏 iterator，调用者通常看不到底层 iterator 失效；但引用、指针和从 front() 取得的对象别名仍然受底层元素生命周期影响。pop() 删除队首元素后，指向原队首元素的引用和指针立即失效，这个结论与底层使用 deque 或 list 无关，因为对象生命周期已经结束。

下面这个例子展示底层容器替换的合法与非法边界：

#include <deque>
#include <list>
#include <queue>
#include <vector>

std::queue<int> default_queue;                    // uses std::deque<int>
std::queue<int, std::deque<int>> deque_queue;      // valid underlying container
std::queue<int, std::list<int>> list_queue;        // valid underlying container
// std::queue<int, std::vector<int>> vector_queue; // invalid underlying container choice

std::vector<int> 的问题来自端点能力缺口。FIFO 删除发生在队首，std::vector 的接口没有 pop_front()。即使可以用 erase(begin()) 模拟删除首元素，那也会移动后续元素，复杂度和接口语义都无法满足 std::queue 对底层容器的直接转发模型。

底层容器条件还会影响异常安全。push() 会调用底层 push_back()，新元素的构造、移动或分配可能抛出异常。若失败发生在底层容器提交新元素之前，队列保持原有状态；若操作完成，元素已经进入队尾。pop() 通常只销毁队首元素并调整底层容器状态，调用前提是队列非空。对空队列调用 front()、back() 或 pop()，调用者没有满足标准库接口前提，程序行为失去可靠语义。

工程上选择 Container 的顺序应固定：先确认 FIFO 端点操作是否存在，再确认元素类型一致，再评估端点操作复杂度，然后评估元素生命周期、引用稳定性和内存布局。这个顺序能把“能不能实例化”和“值不值得使用”分开判断。

23.3 push、pop、front 与 back 的状态路径

push()、pop()、front() 和 back() 是 std::queue 的状态主路径。push() 在队尾构造或移动一个新元素；front() 返回队首元素引用；back() 返回队尾元素引用；pop() 删除队首元素。队列自身没有“取出并返回元素”的成员函数，读取和删除分成两步由调用者组合。

贯穿例子中的循环采用了安全的两步写法：

void drain_jobs(std::queue<Job>& jobs) {
    while (!jobs.empty()) {
        Job current = std::move(jobs.front());
        jobs.pop();
        run(std::move(current));
    }
}

第一步 std::move(jobs.front()) 把队首元素作为右值表达式传给 Job 的移动构造函数。移动完成后，队首元素仍然存在于队列内部，只是处于 moved-from 状态。第二步 jobs.pop() 删除这个队首元素，触发析构并推进底层容器的起点。第三步 run(std::move(current)) 处理已经脱离队列的局部对象。

这三个动作的先后顺序有明确意义。若先调用 pop()，队首对象已经被销毁，后续无法读取原元素。若保存 front() 的引用再调用 pop()，引用指向的对象生命周期结束，继续使用该引用会访问已失效对象。下面的代码展示这个风险边界：

void wrong(std::queue<Job>& jobs) {
    Job& ref = jobs.front();
    jobs.pop();
    run(ref); // ref no longer denotes a live queue element
}

正确判断方式是把 front() 返回值看成“队列内部当前队首对象的别名”。只要对象还在队列中，这个别名可以读取或修改队首元素；pop() 完成后，这个别名失去对象生命周期支撑。对大型对象或 move-only 对象，先 move 到局部对象，再 pop()，可以把生命周期边界写清楚。

back() 用来观察最新入队元素。它常见于调试、确认批量入队结果、维护队尾状态等场景。back() 与 front() 一样返回引用，因此它也受队列修改和对象生命周期约束。调用 push() 后，back() 指向新队尾；调用 pop() 删除的是队首，队尾通常保持业务意义上的“最新元素”。若队列只有一个元素，pop() 后队列为空，原来的 front 和 back 同时消失。

push() 有拷贝和移动两个常见入口。传入左值时，新元素从实参拷贝构造；传入右值时，新元素可以移动构造；使用 emplace() 时，构造参数直接转发到底层容器的 emplace_back()。这些入口改变的是队尾元素的构造方式，FIFO 端点语义保持一致。

std::queue<Job> jobs;

Job parse{1, "parse"};
jobs.push(parse);                    // copy into the back
jobs.push(Job{2, "index"});          // move into the back
jobs.emplace(Job{3, "flush"});       // constructs through the adaptor interface

Job& first = jobs.front();            // id == 1
Job& last = jobs.back();              // id == 3

emplace() 在 queue 中的语义仍然是“在队尾构造”。它减少一次临时对象构造的机会，但它没有改变顺序模型。C++23 增加的 push_range 也是把一段元素追加到队尾，适合批量入队；它同样服务 FIFO 顺序。C++26 对 constexpr queue 的推进影响常量求值可用性，但本章关注的端点转发模型保持不变。

23.4 iterator 封装边界与顺序语义

std::queue 公开接口没有 begin() 和 end()。这一点直接服务 FIFO 语义：调用者可以查看队首和队尾，可以查询大小，可以入队和出队，但无法遍历中间元素，也无法对中间元素排序、删除或重排。适配器通过隐藏 iterator，把底层容器的结构能力从调用者手中收回。

这种封装带来一个清晰的工程后果：std::queue 适合表达“处理者只关心下一个元素”的场景。若业务需要遍历所有等待元素、按条件删除中间元素、查找某个未处理元素或重新排序，公开接口已经提示当前抽象不匹配。此时应回到底层容器、选择其他容器，或设计一个明确暴露遍历能力的队列类型。

下面这段代码展示 std::queue 对遍历的限制：

std::queue<int> values;
values.push(10);
values.push(20);
values.push(30);

while (!values.empty()) {
    int current = values.front();
    values.pop();
    // process current
}

处理队列中所有元素的标准方式是重复读取 front() 并调用 pop()。这个过程会消耗队列内容。如果业务只想查看元素而保留队列，std::queue 本身没有提供无损遍历接口。可以拷贝一份队列再弹出副本，但这会引入元素拷贝、移动和额外内存成本；也可以直接使用 std::deque 或 std::list 保存等待元素，并在类型命名和接口约束中表达业务意图。

iterator 封装也影响算法集成。传统 STL 算法通常接收半开区间 [first, last)，需要迭代器作为输入。std::queue 没有公开迭代器，因此无法直接传给 std::find、std::sort、std::remove_if 等算法。这个限制是类型接口的一部分，读源码时可以把它理解成“适配器公开端点操作，底层容器保留结构细节”。

从源码形状看，std::queue 通常只有一个受保护的底层成员 c。继承者可以在派生类中访问它，但工程代码很少通过继承 std::queue 暴露内部容器。更稳定的做法是直接选择符合需求的容器类型：需要 FIFO 就使用 std::queue，需要遍历和中间删除就使用 std::deque 或 std::list 并把操作规则写在业务层。

顺序语义的检查顺序可以固定为四步：第一，看业务是否只处理队首；第二，看新元素是否总是追加到队尾；第三，看是否需要观察或修改中间元素；第四，看处理过程是否会消耗队列。四步都落在 FIFO 端点模型上，std::queue 才是合适抽象。

23.5 工程使用场景

std::queue 最适合表达“等待项按到达顺序处理”的局部结构。它的价值来自接口约束：调用者只能从队尾加入，从队首取出。只要业务规则可以接受这个顺序，std::queue 就能减少错误操作的入口。

任务队列是最直接的场景。生产者把 Job 追加到队尾，消费者从队首取出下一个任务。单线程任务队列可以直接使用 std::queue<Job>；多线程生产消费模型还需要互斥锁、条件变量或专门的并发队列。标准 std::queue 只管理元素顺序和底层存储，它没有内置同步，也没有阻塞等待语义。

#include <condition_variable>
#include <mutex>
#include <queue>

class JobQueue {
public:
    void push(Job job) {
        {
            std::lock_guard<std::mutex> lock(mutex_);
            jobs_.push(std::move(job));
        }
        ready_.notify_one();
    }

    Job wait_and_pop() {
        std::unique_lock<std::mutex> lock(mutex_);
        ready_.wait(lock, [this] { return !jobs_.empty(); });
        Job job = std::move(jobs_.front());
        jobs_.pop();
        return job;
    }

private:
    std::mutex mutex_;
    std::condition_variable ready_;
    std::queue<Job> jobs_;
};

这个例子中，std::queue 只负责 FIFO 存储；std::mutex 负责互斥访问；std::condition_variable 负责等待非空状态。三个角色不能混写。若队列需要容量上限，还要额外维护 max_size 检查和“非满”条件。把这些责任分开，代码才能看清每个同步条件对应哪个状态。

广度优先搜索（BFS）是另一个典型场景。BFS 需要先处理距离起点更近的节点，再处理下一层节点。把新发现的邻居追加到队尾，从队首取出下一个待访问节点，就可以自然形成按层推进的顺序。

#include <queue>
#include <vector>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<char> visited(graph.size(), false);
    std::queue<int> pending;

    visited[start] = true;
    pending.push(start);

    while (!pending.empty()) {
        int node = pending.front();
        pending.pop();

        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                pending.push(next);
            }
        }
    }
}

这段 BFS 代码的队列含义非常明确：pending 中保存已经发现、等待处理的节点。front() 给出当前层最早发现的节点，push() 把下一批节点追加到未来处理序列。若把容器换成 std::stack，遍历会变成深度优先倾向；若换成 std::priority_queue，处理顺序会由优先级决定。容器适配器选择直接改变算法语义。

事件缓冲也适合 std::queue。输入事件、网络包、日志项或 UI 消息通常按到达顺序进入缓冲区，处理端按同样顺序消费。这里需要额外关注两个边界：第一，事件生产速度长期超过消费速度时，队列会持续增长；第二，事件处理需要查看未来事件或合并中间事件时，单纯 FIFO 接口会限制优化空间。前者需要容量策略和背压设计，后者通常需要选择可遍历容器或专门的事件缓冲结构。

工程选型可以按下面顺序判断：先确认业务顺序是否为 FIFO，再确认是否需要遍历或中间删除，然后确认并发访问是否需要同步，接着确认队列长度是否需要上限，最后评估底层容器的内存布局和端点操作成本。这个顺序把语义、接口、同步、容量和性能分开检查，能覆盖大多数 std::queue 使用决策。

最小自检任务

判断下面三个声明或用法是否适合表达 FIFO 队列，并说明理由。要求从底层容器能力、端点操作、对象生命周期和工程语义四个角度回答。

#include <deque>
#include <list>
#include <queue>
#include <vector>

struct Job {
    int id;
};

std::queue<Job> q1;
std::queue<Job, std::list<Job>> q2;
// std::queue<Job, std::vector<Job>> q3;

void consume(std::queue<Job>& jobs) {
    Job& ref = jobs.front();
    jobs.pop();
    Job copy = ref;
}

答案要点

q1 适合表达通用 FIFO 队列。它使用默认底层容器 std::deque<Job>，具备 front()、back()、push_back() 和 pop_front()，入队和出队正好映射到队尾与队首。

q2 也能表达 FIFO 队列。std::list<Job> 满足所需端点接口，节点式布局会改变内存分配、缓存局部性和引用稳定性。选择它需要有节点稳定性或元素移动成本方面的理由。

q3 的底层容器选择不成立。std::vector<Job> 没有 pop_front()，无法支撑 std::queue 的 pop() 转发路径。用 erase(begin()) 模拟队首删除会移动后续元素，已经偏离 queue 的底层容器要求。

consume() 的生命周期处理有错误。ref 是队首元素的引用，jobs.pop() 删除队首元素后，ref 已经失去有效对象支撑。正确写法应先把队首元素拷贝或移动到局部对象，再调用 pop()。

void consume(std::queue<Job>& jobs) {
    Job copy = jobs.front();
    jobs.pop();
}

对 move-only 或移动成本更低的元素，可以写成 Job current = std::move(jobs.front()); jobs.pop();。判断顺序是：确认队列非空，读取或移动队首对象，删除队首对象，再使用已经脱离队列的局部对象。

本章知识点总结

• FIFO 语义：std::queue 表达先进入、先离开的顺序约束，新元素从队尾进入，旧元素从队首离开。
• 适配器目标：std::queue 通过包装底层容器，把多种容器能力收窄成队列接口。
• 默认 deque：std::queue<T> 默认使用 std::deque<T>，因为它支持队首读取和删除，也支持队尾写入。
• 容器条件：底层容器需要提供 front()、back()、push_back() 和 pop_front()，且 value_type 与队列元素类型一致。
• vector 边界：std::vector 缺少 pop_front()，不能作为合格的 std::queue 底层容器。
• push 路径：push() 和 emplace() 都把新元素放到队尾，区别只在元素构造方式。
• front 路径：front() 返回队首元素引用，适合读取或移动即将出队的对象。
• pop 路径：pop() 删除队首元素并结束其生命周期，返回类型是 void。
• 引用边界：从 front() 或 back() 得到的引用依赖队列内部元素生命周期，相关元素被删除后引用立即失效。
• iterator 封装：std::queue 没有公开 begin() 和 end()，调用者无法直接遍历或修改中间元素。
• 算法边界：传统 STL 算法需要迭代器区间，std::queue 需要通过反复 front() 与 pop() 消费元素。
• 同步边界：std::queue 管理 FIFO 顺序和底层存储，多线程生产消费还需要互斥、条件变量或并发队列。
• 容量边界：标准 std::queue 没有内置容量上限，事件缓冲和生产消费场景需要额外背压策略。
• 选型顺序：先判断 FIFO 语义，再检查遍历需求、同步需求、容量策略和底层容器成本。