大家好，这里是彩妙呀~

在STL中，除了stack - 栈这种“后进先出”的容器，还有两种极为实用的队列适配器：queue（队列）和priority_queue（优先队列）。

<注意：STL中的容器适配器只有stack，queue与priority_queue>

queue严格遵循先进先出（FIFO）原则，就像生活中排队买票——先来的人先服务。它默认基于deque实现，提供push（入队）、pop（出队）、front/back访问队首队尾等简洁操作，常用于任务调度、广度优先搜索（BFS）等需要按顺序处理的场景。

priority_queue则打破了“先来后到”的规则，让优先级高的元素“插队”先出。它基于vector实现，默认是大根堆（最大元素优先），你也可以自定义比较规则变成小根堆。通过push插入元素、pop弹出优先级最高的元素、top访问该元素，它在堆排序、Dijkstra最短路径等算法中扮演关键角色。

官方文档解释 queue 头文件https://cplusplus.com/reference/queue/下面，彩妙将会带着大家深入探索这两个队列适配器的使用与原理。

---

队列 queue：先进先出的线性数据结构

queue介绍：--- 参考文档

queue，是一种FIFO（First In First Out）队列。他的底层逻辑与stack一样，是一种队列容器适配器。

什么是容器适配器？

下面的文章可以解决这个问题：

C++：吃透容器适配器https://blog.csdn.net/weixin_66776566/article/details/157982117?spm=1001.2014.3001.5501如果想了解有关stack知识的小伙伴也可以看下面的文章：

STL精讲：stack容器适配器https://blog.csdn.net/weixin_66776566/article/details/158316325?spm=1001.2014.3001.5501学过数据结构这门课程的小伙伴：对应queue来说，就是C++中的队列。

---

下面是官方文档的解释

queue队列是一种容器适配器，专门设计用于先进先出（FIFO）场景，即元素从容器一端插入，从另一端提取。

队列作为容器适配器实现，其本质是使用特定容器类的封装对象作为底层容器的类，通过提供特定的成员函数集来访问元素(通常来说，queue底层默认的容器为deque)。元素被推入（push）到底层容器的"尾部"，并从其"头部"弹出（pop）。

底层容器可以是标准容器类模板之一，或其他专门设计的容器类。但该底层容器必须至少支持以下操作：

• empty（判空）

• size（大小）

• front（访问队首）

• back（访问队尾）

• push_back（尾部插入）

• pop_front（头部删除）

标准容器类deque（双端队列）和list（链表）满足这些要求。默认情况下，若未为特定队列类实例化指定容器类，将使用标准容器deque。

---

queue头文件与声明

我们要使用queue，要包含的头文件：

#include <queue>   // 使用 queue 必须包含此头文件

这个头文件不仅包含了std::queue（队列容器适配器），也包含了std::priority_queue（优先队列容器适配器）

但由于queue是一个容器适配器，所以我们也可以自定义他的底层容器（如果使用其他类作为底层容器，要注意引入包含这个类的头文件）：

//官方声明的queue
template <class T, class Container = deque<T> > class queue;

//提前声明头文件
#include <queue>
//queue命名的格式
std::queue<T,Container> que;

//使用默认的底层容器来存储int
std::queue<int> que_int;

//使用list作为底层容器
#include <list>
std::queue<double,std::list<double>> que_double;

T：队列中存储的元素类型。

Container：底层使用的容器类型。默认值为 std::deque<T>。
该容器必须支持以下操作（queue 会调用这些成员函数来实现自己的接口）：

• push_back(const T&) 或 push_back(T&&) （用于 queue::push）

• pop_front() （用于 queue::pop）

• front() 和 back() （用于 queue::front 和 queue::back）

• empty() 和 size() （用于 queue::empty 和 queue::size）

• 此外，为了支持 emplace，容器需要提供 emplace_back（C++11 起）。

符合这些要求的 STL 容器包括：

• std::deque （默认，双端队列）

• std::list （双向链表）

• （不可以使用 std::vector，因为 vector 没有 pop_front 操作）

因此，你可以自定义底层容器，只要它满足上述接口。

queue中的核心接口

queue中这些接口都与stack中类似。想详细看看的小伙伴可以看彩妙之前的文章~

push 和 emplace

这两个函数用于在队尾插入元素。push 是将元素拷贝或移动到队列中，而 emplace 则是直接在队列尾部构造元素，避免了不必要的拷贝和移动操作，效率更高。例如：

std::queue<int> q;

q.push(1); // 拷贝或移动1到队尾

q.emplace(2); // 直接在队尾构造2

pop

用于删除队首元素，但该函数不会返回被删除的元素。如果需要获取并删除队首元素，应先调用 front 获取元素，再调用 pop 删除。例如：

if (!q.empty()) {

    int frontElement = q.front(); // 获取队首元素

    q.pop(); // 删除队首元素

}

front 和 back

front 用于访问队首元素，back 用于访问队尾元素。这两个函数在调用前需要确保队列不为空，否则会导致未定义行为。例如：

if (!q.empty()) {

    int frontElement = q.front(); // 安全访问队首元素

    int backElement = q.back(); // 安全访问队尾元素

}

empty 和 size

empty 用于判断队列是否为空，size 用于返回队列中元素的个数。这两个函数的时间复杂度都为 O (1)。例如：

bool isEmpty = q.empty(); // 判断队列是否为空

size_t queueSize = q.size(); // 获取队列元素个数

对于新手来说，容易犯的错误是在队列可能为空的情况下直接调用 front、back 或 pop 函数，这会导致程序崩溃或出现未定义行为。正确的做法是在进行这些操作之前，先使用 empty 函数判断队列是否为空。例如：

// 错误示范，可能导致未定义行为

int wrongFront = q.front();

q.pop();

// 正确示范，先判空再操作

if (!q.empty()) {

    int rightFront = q.front();

    q.pop();

}

queue应用：简单了解

queue（队列）的 FIFO 特性可以在下述的场景广泛应用：

• 任务调度：打印机任务队列、线程池任务排队，按请求顺序处理。

• 广度优先搜索（BFS）：图/树遍历时用队列保存待访问节点。

• 缓冲处理：消息队列、数据流缓冲，平衡生产者和消费者速度。

• 模拟系统：银行/医院排队叫号系统，按到达顺序服务。

优先队列 priority_queue：按优先级排序的 “特殊队列”

priority_queue 的本质：基于堆的适配器

优先队列（priority_queue）是 C++ STL 里一种特殊的容器适配器。它和普通队列最大的不同是：普通队列讲究“先来后到”（FIFO），而优先队列讲究“谁重要谁先走”。它的底层实现基于堆（heap）数据结构，而堆通常用 vector 来存储（堆是一种特殊的二叉树）。

默认情况下，priority_queue 是一个大根堆，也就是堆顶的元素永远是整个队列中最大的那个。当你调用 pop() 时，被移除的就是这个最大的元素（也就是优先级最高）。

比如，我们把 {3, 1, 4, 1, 5, 9} 依次插入优先队列，内部会自动调整成大根堆，堆顶始终是当前的最大值。

从实现原理上讲，priority_queue 利用堆的性质，保证插入（push）和删除（pop）操作的时间复杂度都是 O(log n)。

举个生活中的例子：假如你有一个任务调度系统，每个任务都有优先级，用优先队列就能瞬间拿到优先级最高的任务去执行，而不必遍历整个任务列表。

priority_queue声明与定义 --- priority_queue的构造

构造一个优先队列很简单，最常用的就是默认构造：

#include <queue>
std::priority_queue<int> pq;   // 默认大根堆，元素越大越先出队

如果想改成小根堆，可以使用仿函数来解决：

//第三个传参是仿函数
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

常用操作：接口与使用规范

优先队列的成员函数非常简洁，和普通队列类似，但少了 back()，因为堆结构里没有“队尾”的概念。

• push(x)：将元素 x 插入队列，内部自动调整堆。

• pop()：删除堆顶元素（优先级最高的那个），但不返回该元素。

• top()：返回堆顶元素的引用（只读），不删除。

• empty()：判断队列是否为空。

• size()：返回队列中元素的个数。

使用时的标准流程是：先 top() 拿到元素，再 pop() 移除它。例如：

while (!pq.empty()) {
    int val = pq.top();   // 获取当前最大值
    pq.pop();             // 删除它
    // 处理 val...
}

queue 与 priority_queue 的核心区别

queue 和 priority_queue 虽然都属于容器适配器，但在底层容器选择、数据操作规则以及性能表现上存在显著差异，下面通过表格进行详细对比：

对比维度	queue	priority_queue
底层默认容器	deque	vector
选择原因	deque 在两端进行插入和删除操作的时间复杂度为 O (1)，非常适合 queue 先进先出的特性。它的内存布局是分段连续的，通过中控器管理内存块，避免了 vector 在扩容时的大量数据迁移，也解决了 list 内存不连续导致的缓存命中率低的问题	vector 具有连续的内存布局，这使得它在随机访问时效率很高，并且 vector 支持快速的尾部插入和删除操作，这对于维护堆结构非常重要。堆的调整操作（如插入和删除元素后的堆化）依赖于随机访问来高效地定位和调整元素
数据操作规则	先进先出（FIFO），从队尾插入元素（push 或 emplace），从队首删除元素（pop），只能访问队首（front）和队尾（back）元素	根据元素的优先级进行排序，默认情况下是大根堆（优先级最高的元素在队首）。每次插入元素（push）后，会自动调整堆结构以保持堆的性质；删除元素（pop）时，总是删除队首（优先级最高）的元素，只能访问队首（top）元素
时间复杂度	push、pop、front、back、empty、size 操作的时间复杂度均为 O (1)，因为 deque 的相关操作效率高	push 和 pop 操作的时间复杂度为 O (log n)，这是由于在插入和删除元素时需要调整堆结构，以维护堆的性质。top、empty、size 操作的时间复杂度为 O (1)

---

本篇到这里就结束了，喜欢文章的小伙伴可以关注一下彩妙，我们下一篇再见~