C++ STL 队列详解：queue 的使用、经典应用与简单模拟实现

🔥 星恒随风： 个人主页 ❄️ 个人专栏： 《指针合集》 ｜ 《C语言基础》 ｜ 《数据结构》 ｜ 《机器学习导论》 ｜ 《前端基础》 ｜ 《python基础》 ｜ 《C++从入门到入土》 ✨ 数据即知识，压缩即智能

---

前言

生活中排队是一件很常见的事。

先到的人先接受服务，后到的人排在队尾等待。数据结构中的队列，也是按照类似的规则工作：

先进先出
First In First Out
FIFO

C++ STL 提供了 queue 容器适配器，可以直接实现队尾入队、队头出队。

它的接口看起来很简单，但在算法和工程中使用非常广泛，例如：

• 广度优先搜索
• 二叉树层序遍历
• 任务调度
• 消息缓冲
• 请求排队
• 打印任务管理
• 生产者和消费者模型

本文从 queue 的基本接口开始，逐步讲解它的底层要求、典型应用、两个栈实现队列，以及一个简化版 queue 的模拟实现。

---

一、什么是队列？

队列是一种操作受限的线性数据结构。

假设依次执行：

push(1);
push(2);
push(3);

队列中的顺序是：

队头 -> 1 2 3 <- 队尾

执行一次 pop() 后，最先进入的 1 被删除：

队头 -> 2 3 <- 队尾

因此：

入队顺序：1 2 3
出队顺序：1 2 3

这就是先进先出。

---

二、queue 也是容器适配器

和 stack 一样，queue 也不是一个独立的序列容器，而是容器适配器。

它通过封装底层容器，只提供符合队列规则的操作：

push()
pop()
front()
back()
empty()
size()

队列需要从队尾插入，从队头删除，所以底层容器至少要支持：

front()
back()
push_back()
pop_front()
empty()
size()

deque 和 list 都能满足这些要求。

默认情况下：

std::queue<int>

近似于：

std::queue<int, std::deque<int>>

也可以指定 list：

std::queue<int, std::list<int>> q;

普通 vector 不适合作为标准队列的底层容器，因为它没有 pop_front()，在头部删除元素通常还要搬移后面的数据。

---

三、queue 的常用接口

使用队列需要包含：

#include <queue>

常见接口如下：

接口	作用
queue()	构造空队列
empty()	判断队列是否为空
size()	返回队列中的元素个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push(x)	从队尾插入元素
pop()	删除队头元素
emplace(...)	在队尾直接构造元素
swap()	交换两个队列

基本示例：

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

int main()
{
    queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    cout << "队头：" << q.front() << '\n';
    cout << "队尾：" << q.back() << '\n';
    cout << "元素个数：" << q.size() << '\n';

    q.pop();

    cout << "出队后的队头：" << q.front() << '\n';

    return 0;
}

运行结果：

队头：10
队尾：30
元素个数：3
出队后的队头：20

---

四、front 和 back 分别表示什么？

队列有两个重要位置：

front：队头
back ：队尾

例如：

队头                    队尾
 ↓                       ↓
[10] [20] [30] [40]

调用：

q.front()

得到：

10

调用：

q.back()

得到：

40

新元素会从队尾加入：

q.push(50);

结果：

[10] [20] [30] [40] [50]

出队时删除的是队头：

q.pop();

结果：

[20] [30] [40] [50]

这两个方向不能混淆。

---

五、queue 的 pop 同样不返回元素

下面的写法是错误的：

int value = q.pop();

和栈一样，queue::pop() 只负责删除元素，不返回被删除的值。

如果需要得到队头元素，应该先调用 front()：

int value = q.front();
q.pop();

完整写法：

if (!q.empty())
{
    int value = q.front();
    q.pop();

    cout << value << '\n';
}

---

六、如何遍历 queue？

queue 没有提供：

begin()
end()

也不能直接使用范围 for 遍历。

原因和 stack 相同：队列是容器适配器，只允许按照先进先出的规则访问元素。

如果允许任意访问中间位置，就破坏了队列的接口约束。

想按出队顺序查看队列，可以不断读取 front()：

while (!q.empty())
{
    cout << q.front() << " ";
    q.pop();
}

这会清空原队列。

如果想保留原队列，可以先复制：

queue<int> copy = q;

while (!copy.empty())
{
    cout << copy.front() << " ";
    copy.pop();
}

---

七、队列和栈有什么区别？

栈和队列都属于操作受限的线性结构，但规则不同。

栈

后进先出
同一端插入和删除

示意：

push ↓
┌───┐
│ 3 │ ← top / pop
├───┤
│ 2 │
├───┤
│ 1 │
└───┘

队列

先进先出
队尾插入，队头删除

示意：

pop ← [1][2][3] ← push
       ↑     ↑
     front  back

---

八、经典应用：广度优先搜索

队列最典型的算法应用之一是广度优先搜索，也就是 BFS。

BFS 的特点是：

先处理距离起点较近的节点，再处理距离更远的节点。

假设图的连接关系如下：

0 -> 1, 2
1 -> 3
2 -> 4

从节点 0 开始：

1. 先把 0 入队；
2. 处理 0，将 1、2 入队；
3. 接着处理 1、2；
4. 再处理它们扩展出的 3、4。

代码如下：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> bfs(const vector<vector<int>>& graph, int start)
{
    vector<int> result;
    vector<bool> visited(graph.size(), false);
    queue<int> q;

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

    while (!q.empty())
    {
        int current = q.front();
        q.pop();

        result.push_back(current);

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

    return result;
}

int main()
{
    vector<vector<int>> graph{
        {1, 2},
        {3},
        {4},
        {},
        {}
    };

    vector<int> order = bfs(graph, 0);

    for (int node : order)
    {
        cout << node << " ";
    }

    return 0;
}

输出：

0 1 2 3 4

队列保证先加入的相邻节点先被处理，因此搜索会一层一层向外扩展。

---

九、经典应用：二叉树层序遍历

层序遍历同样依赖队列。

基本过程是：

1. 根节点入队；
2. 取出队头节点；
3. 访问当前节点；
4. 将当前节点的左右孩子入队；
5. 重复以上过程。

代码如下：

#include <queue>
#include <vector>
using namespace std;

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

    TreeNode(int value)
        : val(value)
        , left(nullptr)
        , right(nullptr)
    {}
};

vector<int> levelOrder(TreeNode* root)
{
    vector<int> result;

    if (root == nullptr)
    {
        return result;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty())
    {
        TreeNode* current = q.front();
        q.pop();

        result.push_back(current->val);

        if (current->left != nullptr)
        {
            q.push(current->left);
        }

        if (current->right != nullptr)
        {
            q.push(current->right);
        }
    }

    return result;
}

队列中的元素顺序始终与节点所在层次相对应，因此很适合层序遍历。

---

十、用两个栈实现队列

这是一个很经典的问题：

只能使用栈，怎样实现先进先出的队列？

可以准备两个栈：

_in ：负责入队
_out：负责出队

入队时直接压入 _in：

push(1)
push(2)
push(3)

_in 栈顶
   3
   2
   1

出队时，如果 _out 为空，就把 _in 中的元素全部转移到 _out：

_out 栈顶
   1
   2
   3

这时 _out 的栈顶就是最早进入的元素 1。

实现如下：

#include <cassert>
#include <stack>
using namespace std;

class MyQueue
{
public:
    void push(int value)
    {
        _in.push(value);
    }

    int front()
    {
        moveIfNeeded();

        assert(!_out.empty());
        return _out.top();
    }

    void pop()
    {
        moveIfNeeded();

        assert(!_out.empty());
        _out.pop();
    }

    bool empty() const
    {
        return _in.empty() && _out.empty();
    }

private:
    void moveIfNeeded()
    {
        if (!_out.empty())
        {
            return;
        }

        while (!_in.empty())
        {
            _out.push(_in.top());
            _in.pop();
        }
    }

private:
    stack<int> _in;
    stack<int> _out;
};

这里不要每次出队都来回倒腾元素。

只有 _out 为空时，才把 _in 的元素转移过去。这样每个元素最多经历一次进入 _in、一次转入 _out 和一次弹出。

---

十一、简单模拟实现 queue

队列需要底层容器支持：

队尾插入
队头删除
访问队头
访问队尾

因此不能直接使用普通 vector 实现高效队列。

如果用：

vector.erase(vector.begin());

删除队头后，后面的所有元素通常都需要向前移动，效率较低。

更合适的底层容器包括：

deque
list

下面使用默认的 deque 进行简单封装：

#include <cassert>
#include <cstddef>
#include <deque>

namespace bit
{
    template<class T, class Container = std::deque<T>>
    class queue
    {
    public:
        queue() = default;

        void push(const T& value)
        {
            _container.push_back(value);
        }

        void pop()
        {
            assert(!_container.empty());
            _container.pop_front();
        }

        T& front()
        {
            assert(!_container.empty());
            return _container.front();
        }

        const T& front() const
        {
            assert(!_container.empty());
            return _container.front();
        }

        T& back()
        {
            assert(!_container.empty());
            return _container.back();
        }

        const T& back() const
        {
            assert(!_container.empty());
            return _container.back();
        }

        std::size_t size() const
        {
            return _container.size();
        }

        bool empty() const
        {
            return _container.empty();
        }

    private:
        Container _container;
    };
}

测试代码：

#include <iostream>

int main()
{
    bit::queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    while (!q.empty())
    {
        std::cout << q.front() << " ";
        q.pop();
    }

    return 0;
}

输出：

10 20 30

接口对应关系非常清楚：

queue::push  -> container::push_back
queue::pop   -> container::pop_front
queue::front -> container::front
queue::back  -> container::back

---

十二、使用 list 作为底层容器

因为 list 支持高效头删和尾插，也可以用来封装队列：

#include <list>

bit::queue<int, std::list<int>> q;

队列模拟实现本身不需要知道底层究竟是 deque 还是 list。

只要底层容器具备需要的接口：

push_back()
pop_front()
front()
back()
size()
empty()

队列适配器就可以正常工作。

这也是模板和容器适配器结合后的好处：上层数据结构依赖接口，而不是依赖某一种固定实现。

---

十三、为什么默认选择 deque？

queue 需要在两端进行操作：

队尾插入
队头删除

vector 的尾插很快，但头删通常需要搬移后续元素。

list 的头删和尾插都很方便，但每个节点都要额外保存指针，内存布局也比较分散。

deque 采用分段连续存储，具有几个适合队列的特点：

支持高效头插、头删
支持高效尾插、尾删
扩展时通常不需要整体搬移全部元素
空间利用率通常比链表更好

另一方面，queue 本身不需要遍历，也不提供迭代器，因此 deque 复杂迭代器带来的遍历成本并不是主要问题。

可以说，deque 的优点正好符合队列需要，而它的不足又基本不会暴露出来。

---

十四、queue 和 priority_queue 不一样

queue 和 priority_queue 名字相似，但规则完全不同。

普通队列：

按照进入顺序出队
先进先出

优先队列：

按照优先级出队
默认最大元素优先

例如依次插入：

3 1 8 2

普通队列的队头是：

3

默认大堆优先队列的堆顶是：

8

因此，不要把 queue 和 priority_queue 当成同一种结构。

---

十五、常见错误整理

1. 对空队列调用 front、back 或 pop

错误：

queue<int> q;
cout << q.front();

应先判断：

if (!q.empty())
{
    cout << q.front();
}

2. 认为 pop 会返回队头元素

错误：

int value = q.pop();

正确：

int value = q.front();
q.pop();

3. 混淆 front 和 back

front：最早进入、即将出队的元素
back ：最后进入的元素

4. 使用 vector 频繁删除头部元素

下面这种实现可以工作，但效率通常不好：

v.erase(v.begin());

队列更适合使用 deque 或 list。

5. BFS 中入队后才忘记标记

在图的 BFS 中，通常应该在节点入队时立即标记：

visited[next] = true;
q.push(next);

如果等到出队时再标记，同一个节点可能被重复加入队列。

---

十六、queue 的常见使用场景

队列适合处理“先到先处理”或者“按层扩展”的问题，例如：

广度优先搜索
二叉树层序遍历
任务调度
消息队列
网络请求缓冲
打印任务
事件循环
生产者消费者模型
排队叫号系统

判断一个问题是否适合队列，可以问：

先进入的数据，是否应该优先处理？

如果答案是肯定的，通常可以考虑队列。

---

总结

queue 是一种规则简单、应用广泛的数据结构。

学习时需要重点掌握：

1. 队列遵循先进先出规则
2. push 从队尾插入
3. pop 从队头删除
4. front 访问队头，back 访问队尾
5. pop 不返回被删除元素
6. queue 是容器适配器，没有公开迭代器
7. 默认底层容器是 deque
8. BFS 和层序遍历是队列的典型应用

通过简单模拟实现可以看到，队列同样没有重新发明底层存储结构，而是把已有容器的接口重新组织成：

队尾进入
队头离开

理解了这个过程，也就理解了 STL 容器适配器最核心的设计思路。