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():在容器尾部插入元素 标准容器类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)》的学习就先到这里,如果有什么问题,还请指教指教,希望本篇文章能够对你有所帮助,我们下一篇见!!!
如你喜欢,点点赞就是对我的支持,感谢感谢!!!
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。