C++ queue

去食堂窗口打饭、到银行柜台办理业务或者使用打印机依次打印文档时，讲究的都是 “先来后到”：谁先进入队伍，谁就先得到处理，后来的只能排在队伍末尾，如下图所示。

在编写程序时，当我们需要严格按照 “谁先来、谁先处理” 的顺序管理数据时，就可以使用 C++ 标准库提供的 std::queue。queue 在英文中是 “队列、排队” 的意思，遵循的规则简称为 FIFO，也就是 “First In, First Out（先进先出）” 的缩写。

C++ queue 的定义与常用操作

与前面学习的 std::stack 一样，std::queue 也属于容器适配器。它底层默认借助 std::deque 来保存数据，就像一条单向通行的排队通道：所有新元素一律从 “队尾（back）” 进入，而读取和移除待处理元素一律从 “队头（front）” 开始。

使用 std::queue 时，我们需要先在代码开头引入 <queue> 头文件。

语法：

#include <queue>

std::queue<元素类型> 变量名;

说明：

尖括号 <> 里写明队列保存的元素类型即可，比如 std::queue<int> tasks; 就定义了一个保存整数的空队列。作为容器适配器，它同样不支持花括号列表初始化，也没有 clear() 函数，需要清空时直接写 tasks = {}; 赋一个新空队列即可。它的常用成员函数如下表所示。

C++ queue 的基本操作

初学者在使用 std::queue 时，最容易把查看元素的函数名写混：std::stack 是竖着叠放的，所以查看栈顶使用 top()。而 std::queue 是前后排队的，查看最前面的元素要使用 front()，查看最后面的元素使用 back()，并没有提供 top() 函数。

另外要注意，q.pop() 只负责移除队头元素，返回值类型为 void。如果出队前还需要用到队头元素的值，记得先调用 front() 保存下来，再调用 pop() 删除。下面我们通过一个例子来看看具体用法。

示例 1：入队、查看首尾与出队

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> line;

    line.push("Jack");                 // 依次排入队尾
    line.push("Lucy");
    line.push("Tony");

    std::cout << "队头：" << line.front() << '\n';
    std::cout << "队尾：" << line.back() << '\n';

    std::string cur = line.front();    // 先保存队头元素
    line.pop();                        // 再将队头移出队列

    std::cout << "已办理：" << cur << '\n';
    std::cout << "新队头：" << line.front() << '\n';
    return 0;
}

运行结果如下。

队头：Jack
队尾：Tony
已办理：Jack
新队头：Lucy

分析：

在这个例子中，3 位顾客按照 "Jack" → "Lucy" → "Tony" 的先后顺序调用 push() 进入队列。"Jack" 来得最早排在队头，line.front() 返回 "Jack"。"Tony" 来得最晚排在队尾，line.back() 返回 "Tony"。

接着我们先把队头的 "Jack" 保存到变量 cur 中，再调用 line.pop() 将队头移除。当 "Jack" 离开队列后，原本排在第二位的 "Lucy" 就顺势成了新的队头。

在实际运行的程序中，队列经常是 “一边从队头处理旧任务，一边往队尾加入新任务”，最后再配合 while (!q.empty()) 循环把剩余任务依次处理完。我们可以看一下下面这个例子。

示例 2：动态入队与按序处理

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> tasks;
    tasks.push("订单 101");
    tasks.push("订单 102");

    std::cout << "先处理：" << tasks.front() << '\n';
    tasks.pop();               // 订单 101 出队

    tasks.push("订单 103");    // 新订单排入队尾

    while (!tasks.empty()) {
        std::cout << "接着处理：" << tasks.front() << '\n';
        tasks.pop();
    }
    return 0;
}

运行结果如下。

先处理：订单 101
接着处理：订单 102
接着处理：订单 103

分析：

上面代码中，虽然 "订单 103" 是在 "订单 101" 出队之后中途加进来的，但它只能排在队尾，必须等比它先来的 "订单 102" 处理完之后才轮到它。对比 stack 可以很清楚地看出区别：stack 总是先处理最后进来的元素，而 queue 严格保证先来的元素先出队。

为了保证排队秩序，std::queue 同样屏蔽了下标 []、at() 和范围 for 遍历。如果需要保留全部数据反复遍历，我们应该直接使用 std::vector 或 std::deque。同时大家也要分清查看队头的函数名，不要误写成 top()：

// 正确方式
std::cout << tasks.front() << '\n';

// 错误方式
std::cout << tasks.top() << '\n';

C++ queue 的常见应用

在实际开发中，凡是需要按照 “先来后到” 的顺序依次处理数据的场景，都很适合使用 std::queue：

• 排队叫号与任务调度：比如线上客服按顺序接入用户咨询、打印机依次执行打印任务、服务端按先后顺序处理客户端请求。谁先发起请求，谁就先进入队尾等待处理。
• 消息与事件缓冲：当程序在短时间内连续收到多条网络消息、鼠标键盘事件或日志记录时，可以先将它们按到达顺序放入 queue 中暂存，再由后台按顺序一条条取出处理，防止消息乱序。
• 按层遍历数据结构：在数据结构与算法中，按层顺序搜索树或图的节点时，也会固定使用 queue 来存放接下来等待访问的节点。

平时遇到严格按到达先后处理的业务，我们直接使用 std::queue 就可以了。而如果业务中存在紧急任务，需要打破先来后到、按重要程度 “优先处理”，则可以选用优先队列 std::priority_queue。