C++:栈(stack)、队列(queue)、优先级队列(priority_queue)

Sherry_iyao 2024-06-11 11:35:02 阅读 52

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():在容器尾部插入元素 标准容器类vectordeque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heappop_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)》的学习就先到这里,如果有什么问题,还请指教指教,希望本篇文章能够对你有所帮助,我们下一篇见!!!

如你喜欢,点点赞就是对我的支持,感谢感谢!!!

请添加图片描述



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。