C++学习之旅【C++Stack和Queue类介绍—入门指南与核心概念解析】

🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法》

《C++知识内容》《Linux系统知识》

✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介:

引言:前篇文章,小编已经介绍了关于C++List类的相关知识.接下来我将带领大家继续深入学习C++的相关内容!本篇文章着重介绍关于C++Stack和Queue类以及实现Stack和Queue类的接口,那么这里面到底有哪些知识需要我们去学习的呢?废话不多说,带着这些疑问,下面跟着小编的节奏🎵一起学习吧！

目录

• 1.stack的介绍
• 2. stack类的构造函数(constructor)声明
• 3. stack的成员函数
  • 3.1 empty介绍
  • 3.2 size介绍
  • 3.3 top介绍
  • 3.4 push介绍
  • 3.5 emplace介绍
  • 3.6 pop介绍
  • 3.7 swap介绍
• 4.关于stack的一些oj题目
  • 4.1最小栈
  • 4.2栈的压入、弹出序列
  • 4.3验证栈序列
  • 4.4用栈操作构建数组
  • 4.5栈排序
• 5. stack核心框架接口的模拟实现
• 6. queue介绍
• 7. queue类的构造函数(constructor)声明
• 8. queue的成员函数
  • 8.1 empty介绍
  • 8.2 size介绍
  • 8.3 front介绍
  • 8.4 back介绍
  • 8.5 push介绍
  • 8.6 emplace介绍
  • 8.7 pop介绍
  • 8.8 swap介绍
• 9. 关于queue的一些oj题目
  • 9.1用栈实现队列
  • 9.2用队列实现栈
  • 9.3设计循环双端队列
  • 9.4设计前中后队列
  • 9.5有序队列
• 10. queue核心框架接口的模拟实现
• 11. priority_queue的介绍
• 12. priority_queue类的构造函数(constructor)声明
• 13. priority_queue的成员函数
  • 13.1 empty介绍
  • 13.2 size介绍
  • 13.3 top介绍
  • 13.4 push介绍
  • 13.5 emplace介绍
  • 13.6 pop介绍
  • 13.7 swap介绍
• 14. 关于priority_queue的一些oj题目
  • 14.1数组中第K个大的元素
  • 14.2前k个高频元素
  • 14.3数据流中的第k大元素
  • 14.4最接近原点的k个点
• 15. priority_queue核心框架接口的模拟实现
• 16. 适配器介绍
• 17. deque的简单介绍(了解)
  • 17.1 为什么选择deque作为stack和queue的底层默认容器?

1.stack的介绍

stack的文档介绍

这是C++ 标准库中std::stack 的官方文档说明.stack 是C++ STL(标准模板库)中的容器适配器(不是独立容器),它封装了底层容器(默认是 deque),并强制遵循后进先出(LIFO, Last In First Out)的访问规则 —— 只能从栈顶插入、删除和读取元素,无法随机访问栈中的其他元素,也不支持迭代器遍历.
1️⃣模板定义
template <class T, class Container = deque > class stack;
stack 是一个模板类,有两个参数:
T:栈中存储的元素类型(比如 int、string).
Container:底层用来存储数据的容器类型,默认是 deque<T>.你也可以手动指定为 vector 或 list.
2️⃣LIFO stack(后进先出栈)
核心规则:栈是后进先出(Last-In-First-Out)的容器,元素只能从栈顶(容器的一端)插入和取出,不能随机访问中间元素.
3️⃣容器适配器的本质
stack不是一个独立的容器,而是一个容器适配器(container adaptor).
它的底层是封装了一个普通容器(比如默认的 deque),然后只暴露符合栈规则的接口.
入栈(push)和出栈(pop)操作,本质是在底层容器的尾部(back)进行插入和删除,这个尾部就是栈的顶部(top).
4️⃣底层容器的要求
要作为 stack 的底层容器,必须支持以下操作:
empty():判断容器是否为空
size():返回容器元素数量
back():访问容器尾部元素
push_back():在容器尾部插入元素
pop_back():删除容器尾部元素
标准库中的 vector、deque、list 都满足这些要求,因此都可以作为 stack 的底层容器.
默认情况下,stack 会使用 deque,因为它在两端插入/删除的效率很高,是最优选择.

2. stack类的构造函数(constructor)声明

这是C++ 标准库中std::stack 构造函数的官方文档说明.
1️⃣构造函数签名
explicit stack (const container_type& ctnr = container_type());
explicit 关键字:表示这个构造函数不能用于隐式类型转换,必须显式调用,避免意外的类型转换.
参数 ctnr:是底层容器的对象(比如默认的 deque<T>),默认值是 container_type(),也就是默认构造一个空的底层容器.
版本兼容:顶部的 C++98 和 C++11 标签说明这个构造函数在 C++98 就已存在,并在 C++11 中继续支持.
2️⃣核心功能
这个构造函数的作用是创建一个 stack 容器适配器对象.
因为 stack 是容器适配器,它内部会维护一个底层容器来存储数据:
如果构造时传入了 ctnr 参数,内部底层容器会是这个参数的副本;
如果没有传参数,就默认创建一个空的底层容器(比如默认的 deque).
3️⃣参数详解
ctnr
这是底层容器的对象,container_type是stack 模板的第二个参数 Container 的类型别名(比如默认是 deque<T>).
你可以通过这个参数,用一个已有的容器来初始化栈.例如:
deque my_deque = {1,2,3};
stack my_stack(my_deque); // 用已有deque初始化栈
alloc
这是分配器对象,用于底层容器的内存分配.
这个参数仅在分配器类型满足 uses_allocator::value == true 时才会生效,一般日常开发中很少用到.
拷贝构造(隐含说明)
文档最后一行提到的“A stack of the same type…”，指的是支持用另一个同类型的 stack 来构造新的栈(即拷贝构造),例如：
stack s1;
s1.push(10);
stack s2(s1); // 用s1拷贝构造s2

3. stack的成员函数

3.1 empty介绍

这是C++ 标准库中std::stack::empty 成员函数的官方文档说明.
1️⃣函数签名
bool empty() const;
bool：返回值是布尔类型,表示栈是否为空.
const：这是一个只读成员函数,调用时不会修改栈的任何内容.
2️⃣核心功能
这个函数的作用是判断栈是否为空(即栈中元素的数量是否为 0).
因为 stack 是容器适配器,它的 empty() 本质上是调用了底层容器(比如默认的 deque)的 empty() 方法来实现的.
3️⃣参数与返回值
参数：无(none),调用时不需要传入任何参数.
返回值:
true：栈为空(底层容器的大小为 0).
false：栈不为空(底层容器包含至少一个元素).

3.2 size介绍

这是C++标准库中std::stack::size 成员函数的官方文档说明.
1️⃣函数签名
size_type size() const;
size_type：返回值类型,是一个无符号整数类型(通常和 size_t 等价).
const：这是一个只读成员函数,调用时不会修改栈的内容.
2️⃣核心功能
这个函数的作用是返回栈中当前的元素数量。
因为 stack 是容器适配器，它的 size() 本质上是调用了底层容器（比如默认的 deque）的 size() 方法来实现的。
3️⃣参数与返回值
参数：无(none),调用时不需要传入任何参数.
返回值：
返回栈中元素的个数,也就是底层容器的元素数量,类型为无符号整数 size_type.

3.3 top介绍

这是C++标准库中std::stack::top 成员函数的官方文档说明.
1️⃣函数签名(两个重载版本)
value_type& top();
const value_type& top() const;
value_type& top();:返回栈顶元素的可读写引用,用于修改栈顶元素.
const value_type& top() const;:返回栈顶元素的只读引用,仅用于读取,不能修改.
这两个版本在 C++98 中就已存在,并在 C++11 中继续支持.
2️⃣核心功能
这个函数的作用是返回栈顶元素的引用.
因为栈是后进先出(LIFO)的容器,栈顶元素就是最后插入的那个元素.它本质上是调用了底层容器(比如默认的 deque)的 back() 方法来实现的.
3️⃣参数与返回值
参数：无(none),调用时不需要传入任何参数.
返回值：栈顶元素的引用,非 const 版本可修改栈顶,const 版本仅能读取.
4️⃣关键注意事项
调用 top() 前,必须先用 empty() 判断栈是否为空！
如果栈为空时调用 top(),会触发未定义行为(通常导致程序崩溃).

3.4 push介绍

这是C++标准库中std::stack::push 成员函数的官方文档说明.
1️⃣函数签名
void push (const value_type& val);
void：无返回值,执行入栈操作后不返回任何内容.
const value_type& val：参数是要入栈的元素的const引用,避免拷贝开销,同时保证不会修改传入的原始值.
版本兼容：该函数在 C++98 中就已存在,并在 C++11 中继续支持.
2️⃣核心功能
这个函数的作用是在栈顶插入一个新元素,新元素的内容是参数 val 的副本.
因为 stack 是容器适配器,它的 push() 本质上是调用了底层容器(比如默认的 deque)的 push_back() 方法,在容器的尾部(也就是栈的顶部)插入元素.
3️⃣参数与返回值
参数 val：要插入的元素值,value_type 是栈中存储的元素类型(比如 int、string).
返回值：无(none),仅执行插入操作.
4️⃣关键对比
push() 是通过拷贝元素入栈,如果你想更高效地直接在栈顶构造元素(避免拷贝),可以使用 emplace() 方法.

3.5 emplace介绍

这是C++ 标准库中std::stack::emplace 成员函数的官方文档说明.
1️⃣函数签名
template <class… Args> void emplace (Args&&… args);
模板可变参数:class... Args 和 Args&&... args 是 C++11 引入的可变参数模板和完美转发语法,用来接收任意数量、任意类型的参数，并原封不动地转发给元素的构造函数.
void:无返回值,仅执行构造和插入操作.
2️⃣核心功能
这个函数的作用是在栈顶原地构造并插入一个新元素.
和 push() 不同：
push() 是先构造一个临时元素.再将其拷贝/移动到栈顶;
emplace() 则直接在栈顶的内存位置上,用传入的参数构造元素,完全避免了拷贝或移动的开销,效率更高.
因为 stack 是容器适配器,它的 emplace() 本质上是调用底层容器(比如默认的 deque)的 emplace_back() 方法来实现的.
3️⃣参数与返回值
参数 args：用于构造新元素的参数,会被完美转发给元素的构造函数.例如,如果栈存储的是自定义类 Person(构造函数为 Person(string name, int age)),那么 emplace("Alice", 20) 就会用这两个参数直接构造 Person 对象.
返回值:无(none),仅执行构造和插入操作.
4️⃣适用场景
当元素的构造需要多个参数时,emplace() 可以直接传递构造参数,代码更简洁;
当希望避免拷贝/移动开销、追求更高效率时,优先使用 emplace();
如果已经有一个现成的对象需要入栈,使用 push() 更直观.

3.6 pop介绍

这是C++标准库中std::stack::pop 成员函数的官方文档说明.
1️⃣函数签名
void pop();
void：无返回值,执行出栈操作后不返回任何内容.
无参数,调用时不需要传入任何值.
2️⃣核心功能
这个函数的作用是移除栈顶的元素,并将栈的大小减 1.
被移除的元素是最后一个入栈的元素(符合后进先出规则),它的值可以在调用 pop() 前通过 stack::top() 获取.
因为 stack 是容器适配器,它的 pop() 本质上是调用了底层容器(比如默认的 deque)的 pop_back() 方法,删除容器尾部(栈顶)的元素.
元素被移除时,会调用该元素的析构函数,释放其占用的资源.
3️⃣参数与返回值
参数：无(none).
返回值：无(none),仅执行删除操作.
4️⃣关键注意事项
⚠️ 最容易踩的坑：
①**pop() 不返回被删除的元素**:新手常误以为 pop() 会返回栈顶值,实际它仅删除元素.如果需要获取被删除的值,必须先调用 top() 读取,再调用 pop() 删除.
②空栈调用 pop() 会崩溃:调用 pop() 前,必须先用 empty() 判断栈是否为空,否则会触发未定义行为(通常导致程序崩溃).
5️⃣总结
pop() 仅负责删除栈顶元素,不返回任何值.
必须配合 top() 才能获取并删除元素,且调用前必须用 empty() 判空.
底层依赖容器的 pop_back() 实现,会触发元素的析构函数.

3.7 swap介绍

这是C++标准库中std::stack::swap 成员函数的官方文档说明.
1️⃣函数签名
void swap (stack& x) noexcept(/see below/);
void：无返回值,仅执行交换操作.
stack& x：参数是另一个同类型栈的引用,用来和当前栈交换内容.
noexcept(/*see below*/)：该函数是否抛出异常,取决于底层容器的 swap 操作是否是 noexcept(比如默认底层容器 deque 的 swap 是 noexcept,因此 stack 的 swap 也会是 noexcept).
2️⃣核心功能
这个函数的作用是交换当前栈和参数栈 x 的全部内容.
因为 stack 是容器适配器,它的 swap 本质上是调用了底层容器的非成员 swap 函数,直接交换两个栈的底层容器(比如默认的 deque),这个过程通常是 O(1) 时间复杂度(仅交换底层容器的内部指针,不拷贝元素),效率非常高.
3️⃣参数与返回值
参数 x：另一个同类型的 stack 对象(即元素类型 T 和底层容器类型 Container 都必须完全一致).两个栈的大小可以不同.
返回值：无(none),仅执行交换操作.
4️⃣关键注意事项
⚠️ 必须是同类型栈：只有当两个栈的模板参数(元素类型 T 和底层容器 Container)完全相同时,才能调用 swap.例如：
✅ 合法：stack<int> 和 stack<int>(默认底层都是 deque)
❌ 非法：stack<int> 和 stack<int, vector<int>>(底层容器不同)
5️⃣总结
swap() 用于高效交换两个同类型栈的内容,底层依赖容器的 swap 实现,通常是 O(1) 复杂度.
要求两个栈的元素类型和底层容器类型必须完全一致.
是否抛出异常由底层容器的 swap 操作决定.

4.关于stack的一些oj题目

4.1最小栈

classMinStack{public:MinStack(){}voidpush(int val){ _st.push(val);if(_minst.empty()|| val <= _minst.top()) _minst.push(val);}voidpop(){if(_st.top()== _minst.top()) _minst.pop(); _st.pop();}inttop(){return _st.top();}intgetMin(){return _minst.top();}private: stack<int> _st; stack<int> _minst;};

4.2栈的压入、弹出序列

classSolution{public:boolIsPopOrder(vector<int>& pushV, vector<int>& popV){ stack<int> st; size_t pushi =0, popi =0;while(pushi < pushV.size()){// 入栈序列入栈 st.push(pushV[pushi++]);// 栈顶尝试跟出栈序列匹配while(!st.empty()&& st.top()== popV[popi]){ popi++; st.pop();}}return st.empty();}};//1.pushi 指向数据入栈//2.持续让栈里面的数据跟popi指向出栈比较相等,则 popi++,出栈顶数据,直到栈为空或者不匹配//3.结束条件：pushi 走到尾

4.3验证栈序列

classSolution{public:boolvalidateStackSequences(vector<int>& pushed, vector<int>& popped){ stack<int> st;int j =0;// 指向popped序列的当前元素for(int num : pushed){ st.push(num);// 循环检查栈顶是否匹配当前popped元素while(!st.empty()&& st.top()== popped[j]){ st.pop(); j++;}}// 栈为空说明所有元素都按顺序弹出return st.empty();}};

4.4用栈操作构建数组

classSolution{public: vector<string>buildArray(vector<int>& target,int n){ vector<string> res;int i =0;// 指向目标数组的当前元素for(int num =1; num <= n && i < target.size(); num++){ res.push_back("Push");if(num == target[i]){// 当前数字是目标元素，保留在栈中 i++;}else{// 当前数字不是目标元素，弹出栈 res.push_back("Pop");}}return res;}};

4.5栈排序

classSortedStack{private: stack<int> _main;// 主栈：保存有序元素（栈顶最小） stack<int> _temp;// 临时栈：辅助排序public:SortedStack(){// 构造函数：默认初始化两个栈}voidpush(int val){// 把主栈中比val小的元素移到临时栈while(!_main.empty()&& _main.top()< val){ _temp.push(_main.top()); _main.pop();}// 插入当前元素 _main.push(val);// 把临时栈的元素移回主栈while(!_temp.empty()){ _main.push(_temp.top()); _temp.pop();}}voidpop(){if(!_main.empty()){ _main.pop();}}intpeek(){return _main.empty()?-1: _main.top();}boolisEmpty(){return _main.empty();}};

5. stack核心框架接口的模拟实现

#include<iostream>#include<deque>// 默认底层容器#include<vector>// 可替换的底层容器示例usingnamespace std;// 模板参数：T-存储的元素类型，Container-底层容器类型（默认deque）template<classT,classContainer= deque<T>>classStack{public:// 1. 判空：调用底层容器的empty()boolempty()const{return _con.empty();}// 2. 获取大小：调用底层容器的size() size_t size()const{return _con.size();}// 3. 获取栈顶元素：调用底层容器的back()（栈顶对应容器尾部） T&top(){return _con.back();}// const版本：只读栈顶const T&top()const{return _con.back();}// 4. 入栈：调用底层容器的push_back()voidpush(const T& val){ _con.push_back(val);}// C++11 右值引用版本（优化拷贝）voidpush(T&& val){ _con.push_back(move(val));}// 5. 出栈：调用底层容器的pop_back()（仅删除，无返回值）voidpop(){if(!empty()){// 空栈保护（可选，标准库不做保护，调用pop空栈会崩溃） _con.pop_back();}}private: Container _con;// 封装底层容器，对外隐藏实现细节};intmain(){// 1. 默认底层容器（deque） Stack<int> st1; st1.push(10); st1.push(20); st1.push(30); cout <<"栈大小："<< st1.size()<< endl;// 输出 3 cout <<"栈顶元素："<< st1.top()<< endl;// 输出 30 st1.pop(); cout <<"出栈后栈顶："<< st1.top()<< endl;// 输出 20// 2. 自定义底层容器（vector） Stack<int, vector<int>> st2; st2.push(100); st2.push(200); cout <<"vector底层栈顶："<< st2.top()<< endl;// 输出 200return0;}

6. queue介绍

这是C++标准库中std::queue 的官方文档说明.
1️⃣核心定义:FIFO 队列
std::queue 是一个先进先出(FIFO, First-In First-Out)的容器适配器,元素从一端(队尾)插入,从另一端(队首)取出,符合“先入队的元素先出队”的规则.
2️⃣本质:容器适配器
和 std::stack 一样,queue 本身不直接存储数据,而是封装了一个底层容器(默认是 std::deque),所有操作都通过调用底层容器的接口实现:
入队（push）→ 底层容器的 push_back()（队尾插入）
出队（pop）→ 底层容器的 pop_front()（队首删除）
队首元素（front）→ 底层容器的 front()
队尾元素（back）→ 底层容器的 back()
3️⃣底层容器的要求
底层容器必须支持以下操作：
empty()：判断容器是否为空
size()：获取元素个数
front()：访问队首元素
back()：访问队尾元素
push_back()：在尾部插入元素
pop_front()：在头部删除元素
标准库中,std::deque 和 std::list 都满足这些要求,因此 queue 默认使用 std::deque 作为底层容器(兼顾插入/删除效率).
4️⃣模板定义
template <class T, class Container = deque> class queue;
T：队列存储的元素类型（如 int、string）
Container：底层容器类型,默认是 deque<T>,也可以指定为 list<T> 等符合要求的容器.
核心逻辑总结

7. queue类的构造函数(constructor)声明

这是C++标准库中 std::queue 构造函数的官方文档.
1️⃣构造函数签名
explicit queue (const container_type& ctnr = container_type());
explicit：表示这个构造函数不能用于隐式类型转换,必须显式调用(例如不能写 queue<int> q = my_deque;,必须写 queue<int> q(my_deque);).
container_type：是底层容器的类型别名,对应模板参数 Container(默认是 std::deque<T>).
ctnr：可选参数,是一个底层容器对象的引用.如果传入,队列的内部容器会是这个对象的副本;如果不传入,默认会创建一个空的底层容器.
2️⃣核心逻辑
队列是容器适配器,内部会维护一个底层容器对象:
如果你在构造时传入了一个底层容器(如 deque 或 list),队列会复制这个容器的内容作为初始元素.
如果不传入参数,队列会默认初始化一个空的底层容器.
3️⃣参数说明

8. queue的成员函数

8.1 empty介绍

这是C++ 标准库中 std::queue::empty 成员函数的官方文档.
1️⃣函数签名
bool empty() const;
const 修饰:表示这个函数不会修改队列的状态,是只读操作.
返回值:bool 类型,true 表示队列为空,false 表示队列非空.
2️⃣核心功能
这个函数用于判断队列是否为空(即队列中是否没有元素),本质是检查队列的大小是否为 0.
3️⃣实现原理
因为 std::queue 是容器适配器,empty() 函数实际上是直接调用底层容器的 empty() 方法(比如默认底层容器 std::deque 的 empty()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
true：如果底层容器的大小为 0(队列为空).
false：否则(队列中有元素).
5️⃣常见使用场景
在调用 pop()(出队)或 front()(访问队首)之前,通常会先用 empty() 判断队列是否为空,避免空队列操作导致未定义行为(比如崩溃).

8.2 size介绍

这是C++ 标准库中std::queue::size 成员函数的官方文档.
1️⃣函数签名
size_type size() const;
const 修饰：表示这个函数不会修改队列的状态,是只读操作.
size_type：是一个无符号整数类型的别名(通常是 size_t),用来表示容器的大小.
2️⃣核心功能
这个函数用于获取队列中当前的元素数量.
3️⃣实现原理
因为 std::queue 是容器适配器,size() 函数实际上是直接调用底层容器的 size() 方法(比如默认底层容器 std::deque 的 size()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
返回底层容器中的元素数量,也就是队列的大小.
注意：size_type 是无符号类型,所以永远不会是负数.
5️⃣常见使用场景
结合 empty() 判断队列状态(比如 if (!q.empty()) { ... }).
在遍历队列或批量处理元素前,了解队列的元素总数.

8.3 front介绍

这是C++ 标准库中std::queue::front 成员函数的官方文档.
1️⃣函数签名
value_type& front();
const value_type& front() const;
提供了两个版本：
非 const 版本:返回队首元素的可修改引用,可以直接修改队首元素的值.
const 版本:返回队首元素的只读引用,只能读取,不能修改.
value_type 是队列存储元素的类型(比如 queue<int> 中就是 int).
2️⃣核心功能
这个函数用于访问队列的队首元素,也就是队列中“最早入队”的元素,也是下一个会被 pop() 弹出的元素(符合 FIFO 特性).
3️⃣实现原理
因为 std::queue 是容器适配器,front() 函数实际上是直接调用底层容器的 front() 方法(比如默认底层容器 std::deque 的 front()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
返回队首元素的引用.
注意：如果队列为空时调用 front(),会触发未定义行为(比如程序崩溃),因此通常会先用 empty() 判断队列是否为空.
5️⃣常见使用场景
在 pop() 出队前,先获取队首元素的值.
直接修改队首元素(仅当队列是非 const 时).

8.4 back介绍

这是C++ 标准库中std::queue::back 成员函数的官方文档.
1️⃣函数签名
value_type& back();
const value_type& back() const;
提供两个版本:
非 const 版本:返回队尾元素的可修改引用,可以直接修改队尾元素的值.
const 版本:返回队尾元素的只读引用,只能读取,不能修改.
value_type 是队列存储元素的类型(例如 queue<int> 中就是 int).
2️⃣核心功能
这个函数用于访问队列的队尾元素,也就是队列中“最新入队”的元素(最后一个被 push() 入队的元素).
3️⃣实现原理
因为 std::queue 是容器适配器,back() 函数实际上是直接调用底层容器的 back() 方法(比如默认底层容器 std::deque 的 back()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
返回队尾元素的引用。
注意：如果队列为空时调用 back(),会触发未定义行为(比如程序崩溃),因此通常会先用 empty() 判断队列是否为空.
5️⃣常见使用场景
在 push() 入队后,获取最新入队的元素.
直接修改队尾元素(仅当队列是非 const 时).

8.5 push介绍

这是C++ 标准库中std::queue::push 成员函数的官方文档.
1️⃣函数签名
void push (const value_type& val);
const value_type& val：传入要插入的元素的常量引用,避免不必要的拷贝(C++11 还支持右值引用版本 push(value_type&& val) 来进一步优化).
value_type 是队列存储元素的类型(例如 queue<int> 中就是 int).
返回值：void,无返回值.
2️⃣核心功能
这个函数用于在队列的队尾插入一个新元素,新元素会成为队列的最后一个元素(最新入队的元素）),符合队列“先进先出(FIFO)”的特性.
3️⃣实现原理
因为 std::queue 是容器适配器,push() 函数实际上是直接调用底层容器的 push_back() 方法(比如默认底层容器 std::deque 的 push_back()),时间复杂度为 O(1)(deque 的尾部插入是常数时间).
4️⃣参数与返回值
参数：val,要插入的元素的值,元素会被初始化为此值.
返回值：无(none).
5️⃣常见使用场景
向队列中添加新元素,是实现队列“入队”操作的核心接口.
与 pop()(出队)、front()(访问队首)配合,实现完整的队列操作.

8.6 emplace介绍

这是C++标准库中std::queue::emplace 成员函数的官方文档.
1️⃣函数签名
template <class… Args> void emplace (Args&&… args);
模板参数 Args&&... args：可变参数模板,用于接收构造新元素所需的任意参数(右值引用转发,避免拷贝).
返回值：void,无返回值.
2️⃣核心功能
这个函数用于在队列的队尾****原地构造一个新元素,而不是先创建元素再拷贝/移动到队列中.新元素会直接在底层容器的内存空间中构造,因此比 push 更高效(减少了一次拷贝/移动操作).
3️⃣实现原理
因为 std::queue 是容器适配器,emplace() 函数实际上是直接调用底层容器的 emplace_back() 方法(比如默认底层容器 std::deque 的 emplace_back()),并将参数 args 转发给新元素的构造函数,时间复杂度为 O(1).
4️⃣参数与返回值
参数：args,构造新元素所需的参数(会被转发给元素的构造函数).
返回值：无(none).
5️⃣常见使用场景
当队列存储的是自定义类对象时,emplace 可以避免临时对象的创建和拷贝，提升性能.
需要直接用构造函数参数入队时,emplace 比 push 更简洁(无需显式创建对象).

8.7 pop介绍

这是C++ 标准库中std::queue::pop 成员函数的官方文档.
1️⃣函数签名
void pop();
无参数,无返回值.
注意：pop() 仅删除队首元素,不会返回被删除的元素值.如果需要获取元素值,必须先用 front() 读取,再调用 pop() 删除.
2️⃣核心功能
这个函数用于移除队列的队首元素(也就是队列中“最早入队”的元素,与 front() 访问的是同一个元素),队列的大小会减 1.被移除的元素会调用其析构函数释放资源.
3️⃣实现原理
因为 std::queue 是容器适配器,pop() 函数实际上是直接调用底层容器的 pop_front() 方法(比如默认底层容器 std::deque 的 pop_front()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：无(none).
5️⃣常见注意事项
空队列保护：如果队列为空时调用 pop(),会触发未定义行为(比如程序崩溃),因此必须先用 empty() 判断队列是否为空.
与 front() 配合：因为 pop() 不返回值,所以通常会先调用 front() 获取队首元素的值,再调用 pop() 删除元素.

8.8 swap介绍

这是 C++ 标准库中std::queue::swap 成员函数的官方文档.
1️⃣函数签名
void swap (queue& x) noexcept(/see below/);
参数 queue& x：另一个同类型的队列(模板参数 T 和底层容器 Container 必须完全一致),用于和当前队列交换内容.
noexcept：是否为 noexcept 取决于底层容器的 swap 操作是否为 noexcept(比如默认底层容器 deque 的 swap 是 noexcept,因此队列的 swap 也是 noexcept).
返回值：void,无返回值.
2️⃣核心功能
这个函数用于交换当前队列与另一个同类型队列的全部内容,本质是交换它们的底层容器(因为 queue 是容器适配器).交换后,两个队列的元素会完全互换,且时间复杂度由底层容器的 swap 决定(通常是 O(1),比如 deque 的 swap 仅交换内部指针).
3️⃣实现原理
因为 std::queue 是容器适配器,swap() 函数实际上是调用底层容器的非成员 swap 函数,直接交换两个队列的底层容器对象,因此效率极高(无需拷贝元素).
4️⃣参数与返回值
参数:x,另一个同类型的队列(模板参数必须完全匹配),大小可以不同.
返回值:无(none).
5️⃣常见使用场景
需要快速交换两个队列的内容,比逐个元素拷贝高效得多(时间复杂度通常为 O(1)).
在算法中临时交换队列状态,或用于容器适配器的高效重置.

9. 关于queue的一些oj题目

9.1用栈实现队列

classMyQueue{private: stack<int> inStack;// 输入栈：负责入队 stack<int> outStack;// 输出栈：负责出队/查看队首// 将输入栈的元素转移到输出栈（仅当输出栈为空时调用）voidtransfer(){if(outStack.empty()){while(!inStack.empty()){ outStack.push(inStack.top()); inStack.pop();}}}public:MyQueue(){// 构造函数：默认初始化两个栈}voidpush(int x){// 入队：直接压入输入栈 inStack.push(x);}intpop(){// 出队：先确保输出栈有元素，再弹出栈顶transfer();int val = outStack.top(); outStack.pop();return val;}intpeek(){// 查看队首：先确保输出栈有元素，再返回栈顶transfer();return outStack.top();}boolempty(){// 队列为空：两个栈都为空return inStack.empty()&& outStack.empty();}};

9.2用队列实现栈

classMyStack{private: queue<int> q1;// 主队列：存储栈元素，队首 = 栈顶 queue<int> q2;// 临时队列：辅助调整元素顺序public:MyStack(){// 构造函数：默认初始化两个队列}voidpush(int x){// 1. 新元素先入队到临时队列q2 q2.push(x);// 2. 把主队列q1的所有元素移到q2，让新元素到队首while(!q1.empty()){ q2.push(q1.front()); q1.pop();}// 3. 交换q1和q2，让q1成为主队列swap(q1, q2);}intpop(){// 队首就是栈顶，直接弹出int val = q1.front(); q1.pop();return val;}inttop(){// 队首就是栈顶，直接返回return q1.front();}boolempty(){// 主队列为空则栈为空return q1.empty();}};

9.3设计循环双端队列

classMyCircularDeque{private: vector<int> data;int front;int rear;int capacity;public:MyCircularDeque(int k){// 数组容量设为k+1，预留一个空位区分空/满 capacity = k +1; data.resize(capacity); front =0; rear =0;}boolinsertFront(int value){if(isFull()){returnfalse;}// 队首插入：front向前移动一位（循环） front =(front -1+ capacity)% capacity; data[front]= value;returntrue;}boolinsertLast(int value){if(isFull()){returnfalse;}// 队尾插入：先赋值，再移动rear data[rear]= value; rear =(rear +1)% capacity;returntrue;}booldeleteFront(){if(isEmpty()){returnfalse;}// 队首删除：front向后移动一位（循环） front =(front +1)% capacity;returntrue;}booldeleteLast(){if(isEmpty()){returnfalse;}// 队尾删除：rear向前移动一位（循环） rear =(rear -1+ capacity)% capacity;returntrue;}intgetFront(){if(isEmpty()){return-1;}return data[front];}intgetRear(){if(isEmpty()){return-1;}// rear指向队尾的下一个位置，所以取前一个位置return data[(rear -1+ capacity)% capacity];}boolisEmpty(){return front == rear;}boolisFull(){return(rear +1)% capacity == front;}};

9.4设计前中后队列

classFrontMiddleBackQueue{private: deque<int> left; deque<int> right;// 平衡两个队列的大小voidbalance(){// left比right多2个时，将left的最后一个移到right前面if(left.size()> right.size()+1){ right.push_front(left.back()); left.pop_back();}// right比left多1个时，将right的第一个移到left后面elseif(right.size()> left.size()){ left.push_back(right.front()); right.pop_front();}}public:FrontMiddleBackQueue(){}voidpushFront(int val){ left.push_front(val);balance();}voidpushMiddle(int val){// 中间插入到left的队尾if(left.size()> right.size()){ right.push_front(left.back()); left.pop_back();} left.push_back(val);balance();}voidpushBack(int val){ right.push_back(val);balance();}intpopFront(){if(left.empty()&& right.empty())return-1;int val;if(!left.empty()){ val = left.front(); left.pop_front();}else{ val = right.front(); right.pop_front();}balance();return val;}intpopMiddle(){if(left.empty()&& right.empty())return-1;int val = left.back(); left.pop_back();balance();return val;}intpopBack(){if(left.empty()&& right.empty())return-1;int val;if(!right.empty()){ val = right.back(); right.pop_back();}else{ val = left.back(); left.pop_back();}balance();return val;}};

9.5有序队列

核心解题思路(分两步拆解)
第一步：先吃透题目中的操作定义
题目要求的操作是：每次可以选择字符串前 k 个字符中的任意一个,将其移动到字符串末尾.
这个操作的自由度完全由 k 决定——k 越小,操作的限制越大;k 越大,操作的自由度越高.
第二步：分情况分析操作的自由度,推导解法
情况 1：k == 1（操作自由度极低）
因为只能选第一个字符移到末尾(前1个字符里只有这一个选择),所以操作本质是生成原字符串的循环移位.
例如：s = "cba"，操作只能得到：
第1次操作："cba" → 移第一个字符 c 到末尾 → "bac"
第2次操作："bac" → 移第一个字符 b 到末尾 → "acb"
第3次操作："acb" → 移第一个字符 a 到末尾 → "cba"（回到原字符串）
结论：k=1 时无法调整字符的相对顺序,只能遍历所有 n 种循环移位结果,选字典序最小的.
情况 2：k ≥ 2（操作自由度足够高）
这是本题的核心难点，关键结论是：当 k≥2 时,能通过多次操作实现字符的任意重排(等价于排序).
为什么？举个直观例子（以 s = "bac"，k=2 为例）：
我们想把 "bac" 变成 "abc"（最小字典序），操作步骤：
①选前2个字符中的 a（第二个字符）移到末尾 → "bca"
②选前2个字符中的 b（第一个字符）移到末尾 → "cab"
③选前2个字符中的 a（第二个字符）移到末尾 → "cba"
④选前2个字符中的 b（第二个字符）移到末尾 → "cab"（换个思路）
更本质的逻辑：k≥2 时,能实现相邻字符的交换(类似冒泡排序),而能交换相邻字符就意味着可以对整个字符串排序.
结论：k≥2 时,直接对字符串排序就能得到最小字典序(无需复杂操作).
总结
这道题的解题思路核心是根据 k 的值判断操作自由度：
①k=1：操作受限,只能生成循环移位,遍历所有移位结果选最小;
②k≥2：操作无本质限制,直接排序得到最小字典序.

classSolution{public: string orderlyQueue(string s,int k){if(k ==1){// 生成所有循环移位，取字典序最小 string res = s;int n = s.size();for(int i =1; i < n;++i){ string temp = s.substr(i)+ s.substr(0, i);if(temp < res){ res = temp;}}return res;}else{// k >= 2 时，直接排序得到最小字典序sort(s.begin(), s.end());return s;}}};

10. queue核心框架接口的模拟实现

#include<iostream>#include<deque>// 默认底层容器#include<list>usingnamespace std;// 模板参数：T-元素类型，Container-底层容器类型（默认deque<T>）template<classT,classContainer= deque<T>>classQueue{public:// 1. 判空：调用底层容器的empty()，const修饰保证只读boolempty()const{return _con.empty();}// 2. 获取大小：调用底层容器的size()，返回无符号整数 size_t size()const{return _con.size();}// 3. 访问队首元素（可修改版本） T&front(){return _con.front();}// 4. 访问队首元素（只读版本，const对象调用）const T&front()const{return _con.front();}// 5. 访问队尾元素（可修改版本） T&back(){return _con.back();}// 6. 访问队尾元素（只读版本，const对象调用）const T&back()const{return _con.back();}// 7. 入队（队尾插入）：调用底层容器的push_back()voidpush(const T& val){ _con.push_back(val);}// C++11 右值引用版本（优化拷贝，避免临时对象）voidpush(T&& val){ _con.push_back(move(val));}// 8. 出队（队首删除）：仅删除，无返回值；空队列保护（可选）voidpop(){if(!empty()){// 标准库不做保护，空队列pop会崩溃，此处增加容错 _con.pop_front();}}// 9. 交换两个队列的内容：直接交换底层容器voidswap(Queue& other)noexcept{ _con.swap(other._con);// 调用底层容器的swap}private: Container _con;// 封装底层容器，对外隐藏实现细节};// 全局swap函数（适配标准库swap接口）template<classT,classContainer>voidswap(Queue<T, Container>& q1, Queue<T, Container>& q2)noexcept{ q1.swap(q2);}intmain(){// 1. 默认底层容器（deque） Queue<int> q1; q1.push(10); q1.push(20); q1.push(30); cout <<"队列大小："<< q1.size()<< endl;// 输出 3 cout <<"队首元素："<< q1.front()<< endl;// 输出 10 cout <<"队尾元素："<< q1.back()<< endl;// 输出 30 q1.pop();// 出队（删除队首10） cout <<"出队后队首："<< q1.front()<< endl;// 输出 20// 2. 自定义底层容器（list） Queue<int, list<int>> q2; q2.push(100); q2.push(200); cout <<"list底层队列队尾："<< q2.back()<< endl;// 输出 200// 3. 交换两个队列 Queue<int> q3; q3.push(1000);swap(q1, q3); cout <<"交换后q1队首："<< q1.front()<< endl;// 输出 1000return0;}

11. priority_queue的介绍

这是C++ 标准库中std::priority_queue 的官方文档说明.
1️⃣本质:带优先级的容器适配器
std::priority_queue 是一个容器适配器,它不直接存储数据,而是封装了一个底层容器(默认是 std::vector),并通过堆(heap)算法维护元素的优先级顺序,保证队首(堆顶)始终是优先级最高的元素(默认是最大的元素).
2️⃣模板定义
template <class T, class Container = vector, class Compare = less>
class priority_queue;
T：队列存储的元素类型(如 int、string).
Container：底层容器类型(默认是 std::vector,也支持 std::deque),需要支持随机访问迭代器.
Compare：优先级比较规则(默认是 less<T>,即构建大顶堆,队首是最大元素;若改为 greater<T>,则构建小顶堆,队首是最小元素).
3️⃣核心特性
优先级保证：队首元素始终是当前队列中优先级最高的元素(默认按“小于”比较,最大的元素优先级最高).
堆结构维护：插入/删除元素时,自动调用堆算法(make_heap、push_heap、pop_heap)维护堆的结构,时间复杂度为 O(log n).
访问限制：只能访问队首(堆顶)元素,无法随机访问其他位置的元素.
4️⃣底层容器的要求
底层容器必须满足两个条件：
①支持随机访问迭代器:因为堆算法需要随机访问元素来维护堆结构.
②支持核心操作:必须提供 empty()、size()、front()、push_back()、pop_back() 这些接口.
标准库中,std::vector 和 std::deque 都满足这些要求,因此默认使用 std::vector 作为底层容器.
5️⃣核心接口的实现逻辑

6️⃣关键设计思想
适配器模式:通过封装底层容器和堆算法,对外提供“优先队列”的抽象接口,隐藏了堆的实现细节.
灵活性:支持自定义底层容器(如 deque)和比较规则(如小顶堆),适配不同的业务场景.

12. priority_queue类的构造函数(constructor)声明

这是C++标准库中std::priority_queue 构造函数的官方文档.
1️⃣构造函数的核心版本
文档中展示了两个主要的构造函数版本：
①初始化版本(版本1)
explicit priority_queue (const Compare& comp = Compare(), const Container& ctnr = Container());
explicit 修饰：表示不能通过隐式类型转换创建队列,必须显式调用(例如不能写 priority_queue<int> q = my_vector;,必须写 priority_queue<int> q(my_comp, my_vector);).
参数默认值：
comp：默认是 Compare()(默认比较规则为 less<T>,即构建大顶堆).
ctnr：默认是 Container()(默认底层容器为 vector<T>).
核心逻辑：
复制传入的比较对象 comp 和底层容器 ctnr.
调用 make_heap 算法,将底层容器转换为堆结构,保证队列初始就是合法的堆.
②范围初始化版本(版本2)
template
priority_queue (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Container& ctnr = Container());
迭代器范围：接收输入迭代器 [first, last),将该范围内的元素插入到底层容器.
后续逻辑：插入元素后,再调用 make_heap 构造成堆,避免了逐个 push 的 O(n log n) 复杂度,直接通过 make_heap 达到 O(n) 时间复杂度.
2️⃣参数详细解释

3️⃣底层实现逻辑
无论哪个版本的构造函数,最终都会执行以下步骤:
①初始化内部的比较对象和底层容器(复制传入的 comp 和 ctnr).
②若使用范围版本,先将迭代器范围内的元素插入底层容器.
③调用 make_heap 算法,将底层容器转换为堆结构,保证队列初始状态就是合法的堆.

13. priority_queue的成员函数

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中
元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue.注意:默认情况下priority_queue是大堆.

13.1 empty介绍

这是C++标准库中 std::priority_queue::empty 成员函数的官方文档.
1️⃣函数签名
bool empty() const;
const 修饰：表示该函数是只读操作,不会修改优先队列的状态.
返回值：bool 类型,true 表示队列为空,false 表示队列非空.
2️⃣核心功能
这个函数用于判断优先队列是否为空(即队列中元素数量是否为 0),是队列操作前的重要安全检查.
3️⃣实现原理
因为 std::priority_queue 是容器适配器,empty() 函数实际上是直接调用底层容器的 empty() 方法(比如默认底层容器 std::vector 的 empty()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
true：如果底层容器的大小为 0(队列为空).
false：否则(队列中有元素).
5️⃣常见使用场景
在调用 top()(访问队首)或 pop()(删除队首)之前,通常会先用 empty() 判断队列是否为空,避免空队列操作导致未定义行为(比如程序崩溃).

13.2 size介绍

这是C++标准库中std::priority_queue::size 成员函数的官方文档.
1️⃣函数签名
size_type size() const;
const 修饰：表示该函数是只读操作,不会修改优先队列的状态.
size_type：是无符号整数类型的别名(通常为 size_t),用于表示容器的元素数量.
2️⃣核心功能
这个函数用于获取优先队列中当前的元素总数,反映队列的存储规模.
3️⃣实现原理
因为 std::priority_queue 是容器适配器,size() 函数实际上是直接调用底层容器的 size() 方法(比如默认底层容器 std::vector 的 size()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
返回底层容器中的元素数量,即优先队列的大小.
注意：size_type 是无符号类型,因此返回值永远不会为负数.
5️⃣常见使用场景
结合 empty() 判断队列的状态(例如 if (pq.size() > 0) { ... }).
在批量处理元素前,了解队列的元素总数,规划处理逻辑.

13.3 top介绍

这是C++ 标准库中std::priority_queue::top 成员函数的官方文档.
1️⃣函数签名
const value_type& top() const;
两个 const 修饰：
第一个 const：返回值是常量引用,表示不能通过该引用修改队首元素(保证堆结构不被意外破坏).
第二个 const：成员函数是只读操作,不会修改优先队列的状态.
value_type：是队列存储元素的类型(例如 priority_queue<int> 中就是 int).
2️⃣核心功能
这个函数用于访问优先队列的队首(堆顶)元素,该元素是当前队列中优先级最高的元素(默认大顶堆中是最大的元素),也是下一个被 pop() 删除的元素.
3️⃣实现原理
因为 std::priority_queue 是容器适配器,top() 函数实际上是直接调用底层容器的 front() 方法(比如默认底层容器 std::vector 的 front()),时间复杂度为 O(1).
4️⃣参数与返回值
参数：无(none).
返回值：
返回队首元素的常量引用。
注意：如果队列为空时调用 top(),会触发未定义行为(比如程序崩溃),因此必须先用 empty() 判断队列是否为空.
5️⃣常见使用场景
在调用 pop()(删除队首)之前,先通过 top() 获取队首元素的值(因为 pop() 仅删除元素,不返回值).
查看当前队列中优先级最高的元素,而不修改队列状态.

13.4 push介绍

这是C++标准库中 std::priority_queue::push 成员函数的官方文档.
1️⃣函数签名
void push (const value_type& val);
const value_type& val：传入要插入的元素的常量引用,避免不必要的拷贝(C++11 还支持右值引用版本 push(value_type&& val) 进一步优化).
value_type：是队列存储元素的类型(例如 priority_queue<int> 中就是 int).
返回值：void,无返回值.
2️⃣核心功能
这个函数用于向优先队列中插入一个新元素,插入后会自动维护堆的结构,保证队首(堆顶)始终是优先级最高的元素(默认大顶堆中是最大的元素).
3️⃣实现原理
因为 std::priority_queue 是容器适配器,push() 函数的底层执行两步操作:
①插入底层容器：调用底层容器的 push_back()(比如默认底层容器 std::vector 的 push_back()),将新元素添加到容器的末尾。
②维护堆结构：调用 push_heap 算法,对整个容器的元素进行调整,使其重新满足堆的性质.
时间复杂度为 O(log n),因为 push_heap 是对数时间复杂度的操作.
4️⃣参数与返回值
参数：val,要插入的元素的值,元素会被初始化为此值.
返回值：无(none).
5️⃣常见使用场景
向优先队列中添加元素,用于任务调度(高优先级任务优先执行）、TopK 问题(维护前 K 大/小元素)等场景.与 top()、pop() 配合,实现完整的优先队列操作.

13.5 emplace介绍

这是C++ 标准库中std::priority_queue::emplace 成员函数的官方文档.
1️⃣函数签名
template <class… Args> void emplace (Args&&… args);
可变参数模板 Args&&... args：接收构造新元素所需的任意参数(通过右值引用转发,避免不必要的拷贝).
返回值：void,无返回值.
2️⃣核心功能
这个函数用于在优先队列的底层容器中原地构造一个新元素,并自动维护堆的结构,保证队首(堆顶)始终是优先级最高的元素.
和 push 相比,emplace 不需要先创建元素再拷贝/移动到底层容器,而是直接在容器的内存空间中构造元素,因此减少了一次拷贝/移动操作,效率更高.
3️⃣实现原理
因为 std::priority_queue 是容器适配器,emplace() 函数的底层执行两步操作:
①原地构造元素：调用底层容器的 emplace_back()(比如默认底层容器 std::vector 的 emplace_back()),将参数 args 转发给新元素的构造函数,在容器尾部原地构造元素.
②维护堆结构：调用 push_heap 算法,对整个容器的元素进行调整,使其重新满足堆的性质.
时间复杂度为 O(log n),因为 push_heap 是对数时间复杂度的操作.
4️⃣参数与返回值
参数：args,构造新元素所需的参数(会被转发给元素的构造函数).
返回值：无(none).
5️⃣常见使用场景
当队列存储自定义类对象时,emplace 可以避免临时对象的创建和拷贝,显著提升性能.
需要直接用构造函数参数入队时,emplace 比 push 更简洁(无需显式创建对象).

13.6 pop介绍

这是C++ 标准库中std::priority_queue::pop 成员函数的官方文档.
1️⃣函数签名
void pop();
无参数,无返回值.
注意：pop() 仅删除队首(堆顶)元素,不会返回被删除的元素值.如果需要获取元素值,必须先用 top() 读取,再调用 pop() 删除.
2️⃣核心功能
这个函数用于删除优先队列的队首（堆顶）元素,也就是当前队列中优先级最高的元素(默认大顶堆中是最大的元素),队列的大小会减 1.被删除的元素会调用其析构函数释放资源.
3️⃣实现原理
因为 std::priority_queue 是容器适配器,pop() 函数的底层执行两步操作:
①维护堆结构：调用 pop_heap 算法,将堆顶元素移动到底层容器的末尾,并调整剩余元素使其重新满足堆的性质.
②删除元素：调用底层容器的 pop_back()(比如默认底层容器 std::vector 的 pop_back()),删除容器末尾的元素(即原堆顶元素).
时间复杂度为 O(log n),因为 pop_heap 是对数时间复杂度的操作.
4️⃣参数与返回值
参数：无（none）。
返回值：无（none）。
5️⃣常见注意事项
空队列保护：如果队列为空时调用 pop(),会触发未定义行为(比如程序崩溃),因此必须先用 empty() 判断队列是否为空.
与 top() 配合：因为 pop() 不返回值,所以通常会先调用 top() 获取堆顶元素的值,再调用 pop() 删除元素.

13.7 swap介绍

这是C++标准库中std::priority_queue::swap 成员函数的官方文档.
1️⃣函数签名
void swap (priority_queue& x) noexcept (/see below/);
参数 priority_queue& x：另一个同类型的优先队列(模板参数 T、底层容器 Container、比较规则 Compare 必须完全一致),用于和当前队列交换内容.
noexcept 说明：该函数是否为 noexcept 取决于底层容器的 swap 操作和比较函数的 swap 操作是否为 noexcept(例如默认底层容器 vector 的 swap 是 noexcept,因此队列的 swap 通常也是 noexcept).
返回值：void,无返回值.
2️⃣核心功能
这个函数用于完整交换当前优先队列与另一个同类型队列的全部内容,包括：
底层容器的所有元素
内部的比较函数对象
交换后,两个队列的元素和比较规则会完全互换,且时间复杂度由底层容器的 swap 决定(通常为 O(1),因为 vector、deque 等容器的 swap 仅交换内部指针).
3️⃣实现原理
因为 std::priority_queue 是容器适配器,swap() 函数的底层会执行两步操作:
①调用底层容器的非成员 swap 函数,交换两个队列的底层容器.
②调用比较函数的 swap 函数,交换两个队列的比较规则.
这保证了交换操作的高效性,无需拷贝或移动元素.
4️⃣参数与返回值
参数：x,另一个同类型的优先队列(模板参数必须完全匹配),队列大小可以不同.
返回值：无(none).
5️⃣常见使用场景
需要快速交换两个优先队列的内容,比逐个元素拷贝高效得多(时间复杂度通常为 O(1)).
在算法中临时交换队列状态,或用于容器适配器的高效重置.

14. 关于priority_queue的一些oj题目

14.1数组中第K个大的元素

classSolution{public:intfindKthLargest(vector<int>& nums,int k){// 将数组中的元素先放入优先级队列中 priority_queue<int>p(nums.begin(), nums.end());// 将优先级队列中前k-1个元素删除掉for(int i=0; i < k-1;++i){ p.pop();}return p.top();}};

14.2前k个高频元素

classSolution{public: vector<int>topKFrequent(vector<int>& nums,int k){// 1. 统计每个数字的出现频率 unordered_map<int,int> count;for(int num : nums){ count[num]++;}// 2. 小顶堆：按频率从小到大排序，堆顶是频率最小的元素 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;for(auto&[num, freq]: count){ pq.push({freq, num});if(pq.size()> k){ pq.pop();// 堆大小超过 K 时，弹出频率最小的元素}}// 3. 收集结果 vector<int> res;while(!pq.empty()){ res.push_back(pq.top().second); pq.pop();}return res;}};

14.3数据流中的第k大元素

classKthLargest{private:// 小顶堆：存储当前数据流中最大的K个元素，堆顶是第K大元素 priority_queue<int, vector<int>, greater<int>> min_heap;int k_;// 保存K的值public:KthLargest(int k, vector<int>& nums):k_(k){// 初始化：将所有初始元素加入堆，并维护堆的大小为Kfor(int num : nums){ min_heap.push(num);if(min_heap.size()> k_){ min_heap.pop();// 弹出最小的元素，保证堆大小为K}}}intadd(int val){// 若堆大小不足K，直接加入if(min_heap.size()< k_){ min_heap.push(val);}// 若新元素比堆顶大（说明它应该进入前K大），则替换堆顶elseif(val > min_heap.top()){ min_heap.pop(); min_heap.push(val);}// 堆顶就是当前第K大元素return min_heap.top();}};

14.4最接近原点的k个点

classSolution{public: vector<vector<int>>kClosest(vector<vector<int>>& points,int k){// 大顶堆：存储（距离平方，点坐标），按距离平方从大到小排序 priority_queue<pair<longlong, vector<int>>> max_heap;for(auto& point : points){// 计算距离平方（用long long避免溢出）longlong dist_sq =(longlong)point[0]* point[0]+(longlong)point[1]* point[1]; max_heap.push({dist_sq, point});// 堆大小超过K时，弹出最远的点（堆顶）if(max_heap.size()> k){ max_heap.pop();}}// 收集堆内的K个最近点 vector<vector<int>> res;while(!max_heap.empty()){ res.push_back(max_heap.top().second); max_heap.pop();}return res;}};

15. priority_queue核心框架接口的模拟实现

#include<iostream>#include<vector>#include<algorithm>#include<functional>usingnamespace std;// 模板参数：T-元素类型，Container-底层容器（默认vector），Compare-比较规则（默认less）template<classT,classContainer= vector<T>,classCompare= less<T>>classPriorityQueue{public:// 默认构造：空队列PriorityQueue():_con(),_comp(){}// 范围构造：迭代器范围初始化并构建堆template<classInputIterator>PriorityQueue(InputIterator first, InputIterator last):_con(first, last),_comp(){make_heap(_con.begin(), _con.end(), _comp);}// 判空：直接调用底层容器empty()boolempty()const{return _con.empty();}// 获取大小：直接调用底层容器size() size_t size()const{return _con.size();}// 访问堆顶（优先级最高元素）const T&top()const{if(empty()){ cerr <<"Error: priority_queue is empty!"<< endl;abort();}return _con.front();}// 入队：尾插 + 调整堆voidpush(const T& val){ _con.push_back(val);push_heap(_con.begin(), _con.end(), _comp);}// C++11 右值引用版本（优化拷贝）voidpush(T&& val){ _con.push_back(move(val));push_heap(_con.begin(), _con.end(), _comp);}// 出队：调整堆（堆顶移尾部） + 尾删voidpop(){if(empty()){ cerr <<"Error: pop on empty priority_queue!"<< endl;abort();}pop_heap(_con.begin(), _con.end(), _comp); _con.pop_back();}// 交换两个队列：交换底层容器+比较器voidswap(PriorityQueue& other)noexcept{using std::swap;swap(_con, other._con);swap(_comp, other._comp);}private: Container _con;// 底层容器（存储元素） Compare _comp;// 优先级比较器};// 全局swap函数（适配标准库）template<classT,classContainer,classCompare>voidswap(PriorityQueue<T, Container, Compare>& pq1, PriorityQueue<T, Container, Compare>& pq2)noexcept{ pq1.swap(pq2);}intmain(){// 1. 大顶堆（默认less<int>，堆顶是最大元素） PriorityQueue<int> pq1; pq1.push(30); pq1.push(10); pq1.push(20); cout <<"大顶堆堆顶："<< pq1.top()<< endl;// 输出 30 pq1.pop(); cout <<"出队后堆顶："<< pq1.top()<< endl;// 输出 20// 2. 小顶堆（greater<int>，堆顶是最小元素） PriorityQueue<int, vector<int>, greater<int>> pq2; pq2.push(30); pq2.push(10); pq2.push(20); cout <<"小顶堆堆顶："<< pq2.top()<< endl;// 输出 10return0;}

16. 适配器介绍

适配器是一种设计模式,核心作用是接口转换:它将一个已有类/对象的接口,转换成另一个符合业务需求的接口,让原本接口不兼容的组件可以协同工作.
在 C++ 标准库中,最常见的是容器适配器(如 queue、stack、priority_queue),此外还有迭代器适配器(如 reverse_iterator)、函数适配器(如 bind)等.
1️⃣核心特点：以容器适配器为例
C++ 中的容器适配器不直接管理存储,而是封装一个底层容器(如 vector、deque),并通过接口适配,对外提供更简洁、场景化的操作.
①核心逻辑：“封装 + 适配”
封装底层容器：复用现有容器的存储能力(如 deque 的高效增删、vector 的随机访问),避免重复实现存储逻辑.
适配接口：对外提供符合特定场景的极简接口,隐藏底层容器的复杂细节.
比如 queue(队列)是典型的容器适配器：
底层默认封装 deque,但对外只暴露 push（队尾入队）、pop（队首出队）、front（队首）、back（队尾）等 FIFO（先进先出）相关接口。
底层 deque 的 push_back、pop_front 等接口被适配成了队列的操作,上层代码无需关心底层是 deque 还是 vector.
②关键特性

2️⃣典型示例：priority_queue 作为适配器
priority_queue 是基于堆的容器适配器，核心适配逻辑：
①底层容器：默认封装 vector(支持随机访问,适合堆算法).
②堆算法适配：通过 make_heap、push_heap、pop_heap 等算法,将 vector 的接口适配成优先级队列的操作.
③比较器适配：通过自定义比较器(如 less<T>/greater<T>),实现大顶堆/小顶堆的切换.
对外仅暴露 top（堆顶）、push（入队）、pop（出队）等优先级相关接口,底层的堆调整和容器操作完全被隐藏.
3️⃣适配器的价值
适配器本质是“接口的中间层”,它让代码更聚焦于业务场景(如队列、栈、优先队列),而不用关心底层实现细节,同时最大化复用现有代码,提升开发效率和可维护性.

17. deque的简单介绍(了解)

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque.
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高.是vector和list的一种平衡方案.

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组,其底层结构如下图所示:

双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:

那deque是如何借助其迭代器维护其假想连续的结构呢？

底层实现原理
deque 的底层结构分为两部分：
①中控数组(map)：一个动态数组,每个元素是指向缓冲区的指针.
②缓冲区(buffer)：多个固定大小的连续内存块,用于存储实际元素.
随机访问：访问 deque[i] 时,先通过中控数组找到对应的缓冲区,再在缓冲区内偏移找到元素,需两次指针跳转(时间复杂度仍为 O(1),但比 vector 略慢).
双端插入：队首/队尾插入时,若对应缓冲区未满则直接插入;若已满则新增缓冲区并更新中控数组,无需搬迁现有元素.
适用场景
deque 适合需要双端高效增删 + 偶尔随机访问的场景：
①队列/栈的底层容器：C++ 标准库的 queue 和 stack 默认使用 deque 作为底层容器(因为双端操作高效,且无需随机访问时也能保证性能).
②滑动窗口问题：需要在窗口两端添加/删除元素,并随机访问窗口内的元素.
③频繁双端操作的场景：比如任务队列、事件队列,需要快速在头部或尾部添加/取出任务.
deque vs vector vs list 对比

deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构.

17.1 为什么选择deque作为stack和queue的底层默认容器?

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器,比如list.但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为：
①stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作.
②在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高.结合了deque的优点,而完美的避开了其缺陷.

敬请期待下一篇文章内容–>C++拓展学习之反向迭代器实现、计算器实现以及逆波兰表达式!