中等C++6 分钟2,023 字

C++队列(queue)——像排队一样公平有序

C++队列(queue)——先进先出,公平有序的排队工具

队列就像生活中排队买票、打饭、坐公交——先来的人先被服务,后来的人只能在后面排队等着。这种 先进先出(First In First Out,FIFO)​ 的规则,是计算机里最基础的数据结构之一。

在程序里,队列的应用无处不在:打印机任务按提交顺序打印、游戏中的消息队列、广度优先搜索(BFS)遍历地图、操作系统中进程调度……只要需要“先来先服务”,就会用到队列。


生活中的队列

  • 早餐排队​​:食堂窗口前,小明第一个到,打完饭走了;小红第二个到,等她打完饭,小刚才能轮到。食堂阿姨只服务队伍最前面的那个人。
  • 银行叫号​​:你取号后坐在椅子上等待,屏幕上显示“请A001号到3号窗口”。服务完了才会叫下一个号。这就是一个典型的队列——先取号的人先被叫到。
  • 游乐场排队​​:过山车项目排了长长的队伍,工作人员一次放行若干人,先排队的人先上车。

这些场景的共同点:​数据(人、号、任务)只能从一端(队尾)加入,从另一端(队首)移除​​。


队列的核心特点

  1. 只能从队尾添加元素​​(入队,push)
  2. 只能从队首移除元素​​(出队,pop)
  3. 只能查看队首和队尾元素​​(front 和 back)
  4. 不能随意访问中间的元素​——不提供下标操作

正是因为这种严格的限制,队列保证了“先来后到”的顺序不会被破坏。


C++ 中的队列模板

C++ 标准库提供了 queue 容器,它在头文件 <queue> 中定义。你可以把它看作一个“黑盒子”,只能通过几个固定的操作来使用。

常用操作一览

操作 用法 说明
push(x) q.push(3) 将元素 x 添加到队尾(一个人站到队伍最后)
pop() q.pop() 移除队首元素(队伍最前面的人离开)
front() int f = q.front() 返回队首元素的引用(看一眼排在最前面的人)
back() int b = q.back() 返回队尾元素的引用(看一眼排在最后的人)
empty() if (q.empty()) 判断队列是否为空(队伍里有没有人)
size() int n = q.size() 返回队列中元素的个数(排队的人数)

注意​​:front() 和 back() 返回的是引用,可以直接修改队首或队尾的值,但同学们初学阶段一般只读取它们。


代码示例:排队打印数字

下面这个程序模拟了一个简单的数字队列:1、2、3 依次入队,然后按顺序出队。

cpp
#include <iostream>
#include <queue>        // 使用队列需要这个头文件
using namespace std;

int main() {
    queue<int> q;       // 定义一个整型队列,里面存放整数

    // 三个数字依次入队,就像三个人排队
    q.push(1);          // 1号站到队尾
    q.push(2);          // 2号站到队尾(1号后面)
    q.push(3);          // 3号站到队尾(最后)

    cout << "队列大小:" << q.size() << endl;    // 输出 3
    cout << "队首元素:" << q.front() << endl;  // 输出 1(最前面的是1)
    cout << "队尾元素:" << q.back() << endl;   // 输出 3(最后的是3)

    // 依次让所有元素出队
    while (!q.empty()) {
        cout << "当前队首:" << q.front() << endl;
        q.pop();        // 队首的人离开
    }

    return 0;
}

运行结果

队列大小:3
队首元素:1
队尾元素:3
当前队首:1
当前队首:2
当前队首:3

可以看到,出队的顺序和入队的顺序完全一致(先入队的 1 先出来),这就是 先进先出(FIFO)​​​。


新手常见错误

  1. 在空队列上调用 pop()、front() 或 back() 如果队列为空,程序会直接崩溃。使用前一定要用 empty() 检查。 queue<int> q; // 错误:q 为空,调用 front() 会出错 // cout << q.front(); // 正确做法:先判断 if (!q.empty()) { cout << q.front(); }
  2. 忘记处理队列中的全部元素 有时只想让某些元素出队,但忘了循环中的 pop() 会导致死循环。例如: while (!q.empty()) { cout << q.front(); // 只输出,不 pop,永远不结束! }
  3. 试图用下标访问队列中的元素 queue 不支持 q[0] 这样的操作。它是容器适配器,只能通过 front/back 访问两端。
  4. 混淆队列和栈(stack)​ 栈是后进先出(LIFO),队列是先进先出(FIFO)。写代码时注意别把 push 和 pop 的方向搞反。

完整示例:模拟叫号系统

小练习:用队列模拟“叫号系统”:1号顾客先来,2号、3号后来。服务完成后,请打印服务顺序。

下面程序实现了一个简单的叫号系统,顾客拿号后排队,服务员每次叫号时从队首“请走”一位顾客,并输出他被服务的信息。

cpp
#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<int> customerQueue;   // 存储顾客的号码

    // 顾客依次拿号
    customerQueue.push(1);      // 1号顾客先来,排在第一个
    customerQueue.push(2);      // 2号顾客接着来,排在1号后面
    customerQueue.push(3);      // 3号顾客最后来,排在最后

    cout << "=== 开始叫号服务 ===" << endl;

    // 服务所有顾客
    while (!customerQueue.empty()) {
        int currentCustomer = customerQueue.front();  // 看看队首是谁
        cout << "正在服务 " << currentCustomer << " 号顾客" << endl;
        customerQueue.pop();    // 服务完成,请出队伍
    }

    cout << "所有顾客已服务完毕!" << endl;

    // 演示修改队首元素(不常用,但了解一下)
    // 如果想让队首顾客的号码变成100,可以这样:
    // customerQueue.front() = 100;  // 但此时队列为空,不能这么写

    return 0;
}

运行结果

=== 开始叫号服务 ===
正在服务 1 号顾客
正在服务 2 号顾客
正在服务 3 号顾客
所有顾客已服务完毕!

这个例子清晰地展示了先进先出的顺序:1号最先被服务,3号最后。


相关知识点指引

如果你对队列感兴趣,接下来可以学习:

  • 栈(stack)​​​:和队列恰好相反,后进先出。C++ 的 stack 用法与 queue 非常相似,只是没有 back() 只有 top()。
  • 双端队列(deque)​​​:可以在两端插入和删除,功能更强。C++ 的 deque 头文件是 <deque>。
  • 优先队列(priority_queue)​​​:元素会按照优先级排序,而不是严格的先进先出。比如急诊室里按照病情严重程度决定谁先被救治。
  • 广度优先搜索(BFS)​​​:在图或迷宫中,BFS 的核心就是使用队列来逐层遍历。

试着用队列模拟一个简单的“打印机任务队列”:不同文档提交到打印机,打印机按提交顺序打印。你可以在代码里用字符串存储文件名,看看输出顺序是否和提交顺序一致。

同类知识点