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 T, class Container = deque > class stack;

栈是一种容器适配器，专门设计用于在后进先出（后进先出）上下文中操作，其中元素仅从容器的一端插入和提取。

栈—stack被实现为容器适配器，它是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素是从特定容器的“后部”推/弹出的，即堆栈的顶部。底层容器可以是任何标准容器类模板或某些其他专门设计的容器类。

容器应支持以下操作：

emptysizebackpush_backpop_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 < s的栈顶元素 -2，所以s栈进行压栈操作：

第四步操作：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<int> _push; stack<int> s;};

通过：

🍁栈的压入、弹出序列

题目在这：栈的压入、弹出序列

题目给出两个序列vector<int>& pushV, vector<int>& popV，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

注意：题目说明压栈的所有数字都不相等！

那么我们可以设计一个栈_push，通过模拟出栈来解决这个问题。

int popi = 0;int pushi = 0;int len = popV.size();if(len == 0)// 当队列为空时，返回truereturn true;

遍历两个队列vector<int>& pushV, vector<int>& popV

当pushV[pushi] != popV[popi]时，那么说明并没有出栈，只有压栈，那么_push进行压栈操作：

用while循环来控制

while(pushi < len)

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 < len && _push.top() == popV[popi]){ _push.pop(); ++popi;} 当while(pushi < len)结束，最后进行判断第二个序列是否可能为该栈的弹出顺序。很简单，判断_push是否为空或者popi 是否等于len即可。

🍃答案代码

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here int popi = 0; int pushi = 0; int len = popV.size(); if(len == 0) return true; while(pushi < len) { if(pushV[pushi] != popV[popi]) { _push.push(pushV[pushi]); ++pushi; } else { _push.push(pushV[pushi]); ++pushi; while(!_push.empty() && popi < len && _push.top() == popV[popi]) { _push.pop(); ++popi; } } } return popi == len; // return _push.empty(); } stack<int> _push;};

🍁队列—queue

template <class T, class Container = deque > class queue;

队列是一种容器适配器，专门设计用于在 FIFO 上下文（先进先出）中操作，其中元素被插入到容器的一端并从另一端提取。

队列被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素被推入特定容器的后面并从其前面弹出。

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

emptysizefrontbackpush_backpop_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 T, class Container = vector, class Compare = less > class priority_queue;

🍃注意

priority_queue第三个参数有缺省值less，所以priority_queue默认是大堆，如果要建小堆，将第三个模板参数换成greater比较方式，如：

vector<int> v{ 3,2,7,6,0,4,1,9,8,5};priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl; 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。

像是Date日期类的比较（年、月、日）。

你学会了吗？

好啦，本章对于《C++：栈（stack）和队列（queue）》的学习就先到这里，如果有什么问题，还请指教指教，希望本篇文章能够对你有所帮助，我们下一篇见！！！

如你喜欢，点点赞就是对我的支持，感谢感谢！！！