C++：栈（stack）、队列（queue）、优先级队列（priority
hello，各位小伙伴，本篇文章跟大家一起学习《C++：栈（stack）和队列（queue）》，感谢大家对我上一篇的支持，如有什么问题，还请多多指教 ！
文章目录
- :maple_leaf:栈---stack
- :maple_leaf:栈---stack题目：最小栈（来自leetcode）
- :leaves:如果途中出栈
- :leaves:答案代码
- :maple_leaf:栈的压入、弹出序列
- :leaves:答案代码
- :maple_leaf:队列---queue
- :maple_leaf:优先级队列---priority_queue
- :leaves:优先级队列使用
- :leaves:注意
🍁栈—stack
template class stack;
栈是一种容器适配器，专门设计用于在后进先出（后进先出）上下文中操作，其中元素仅从容器的一端插入和提取。
栈—stack被实现为容器适配器，它是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素是从特定容器的“后部”推/弹出的，即堆栈的顶部。底层容器可以是任何标准容器类模板或某些其他专门设计的容器类。
容器应支持以下操作：
- empty
- size
- back
- push_back
- pop_back
标准容器类vector、deque和list满足这些要求。默认情况下，如果没有为特定堆栈类实例化指定容器类，则使用标准容器deque。
栈是后进先出的底层容器，是一个模板类，其逻辑结构：
栈的成员函数以及功能：
🍁栈—stack题目：最小栈（来自leetcode）
题目在这：最小栈
题目会对该栈进行压栈和出栈，要我们随时查找栈里最小的元素，并且规定在常数时间里检索出来并返回。
根据栈的性质—LIFO（后进先出）：
设计两个栈
- _push负责接受所有操作（1.压栈、2.出栈）
- s另一个负责接收最小元素（1.当s为空或者栈顶元素 >= _push压栈元素时压栈，2.当_push出栈元素 == s栈顶元素时出栈，3.获取栈顶元素）
- 测试例子
第一步操作：对_push栈进行压栈（元素为-2），由于一开始s栈为空，所以s进行压栈：
第二步操作：对_push栈进行压栈（元素为0），由于0 > s的栈顶元素 -2，所以s栈不进行操作：
第三步操作：对_push栈进行压栈（元素为-3），由于-3
第四步操作：minStack.getMin();
返回s栈的栈顶元素 -> -3
🍃如果途中出栈
上述例子，在第四步操作minStack.getMin();前_push出栈一次，由于_push出栈元素等于s栈顶元素，所以s也跟着出栈，最后返回结果是-2
🍃答案代码
class MinStack { public: MinStack() { } void push(int val) { s.push(val); if(_push.empty() || _push.top()>=val) { _push.push(val); } } void pop() { int tmp = s.top(); s.pop(); if(_push.top() == tmp) { _push.pop(); } } int top() { return s.top(); } int getMin() { return _push.top(); } stack _push; stack s; };通过：
🍁栈的压入、弹出序列
题目在这：栈的压入、弹出序列
题目给出两个序列vector& pushV, vector& popV，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
注意：题目说明压栈的所有数字都不相等！
那么我们可以设计一个栈_push，通过模拟出栈来解决这个问题。
int popi = 0; int pushi = 0; int len = popV.size(); if(len == 0)// 当队列为空时，返回true return true;
遍历两个队列vector& pushV, vector& popV
- 当pushV[pushi] != popV[popi]时，那么说明并没有出栈，只有压栈，那么_push进行压栈操作：
用while循环来控制
while(pushi
if(pushV[pushi] != popV[popi]) { _push.push(pushV[pushi]); ++pushi; }- 当pushV[pushi] == popV[popi]时，那么说明并存在出栈，先压栈后出栈，那么_push进行压栈出栈操作，出栈结束后还要判断_push栈顶元素是否等于popV[popi]，如果相等则继续出栈（注意，此时_push不能为空，_push为空退出判断，popi > len说明出栈任务结束，退出判断）：
_push.push(pushV[pushi]);// 先压栈 ++pushi; while(!_push.empty() && popi
- 当while(pushi
🍃答案代码
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector& pushV, vector& popV) { // write code here int popi = 0; int pushi = 0; int len = popV.size(); if(len == 0) return true; while(pushi
🍁队列—queue
template class queue;
队列是一种容器适配器，专门设计用于在 FIFO 上下文（先进先出）中操作，其中元素被插入到容器的一端并从另一端提取。
队列被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素被推入特定容器的后面并从其前面弹出。
底层容器可以是标准容器类模板之一或一些其他专门设计的容器类。该底层容器至少应支持以下操作：
- empty
- size
- front
- back
- push_back
- pop_front
标准容器类 deque 和 list 满足这些要求。默认情况下，如果没有为特定队列类实例化指定容器类，则使用标准容器双端队列。
- 逻辑图
队列的成员函数及其功能
🍁优先级队列—priority_queue
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的尾部弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
- 简而言之就是堆：
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
🍃优先级队列使用
template class priority_queue;
🍃注意
- priority_queue第三个参数有缺省值less，所以priority_queue默认是大堆，如果要建小堆，将第三个模板参数换成greater比较方式，如：
vector v{3,2,7,6,0,4,1,9,8,5}; priority_queue q2(v.begin(), v.end()); cout
- priority_queue第三个参数有缺省值less，所以priority_queue默认是大堆，如果要建小堆，将第三个模板参数换成greater比较方式，如：
- 逻辑图
- 当pushV[pushi] != popV[popi]时，那么说明并没有出栈，只有压栈，那么_push进行压栈操作：
