stack queue priority_queuedeque (包含简单实现)

目录1.stack1.1核心接口1.最小栈2.栈的压入和弹出序列2.queue2.1核心接口1.二叉树的层序遍历3.容器适配器4.vector和list的优缺点5.deque5.15.2deque的缺陷5.3为什么选择deque作为stack和queue的底层默认容器6.priority_queue6.1核心接口7.简单模拟实现1.stack2.queue3.priority_queue8.仿函数今天开始我们来进行STL中stack和queue的学习。1.stack通过官方文档我们可以发现这里面的参数与之前的不同stack栈和 queue队列在 C 标准库中确实不是容器而是容器适配器。stack栈后进先出LIFOLast In First Out。最后压入的元素最先弹出就像一摞盘子后放的盘子先被取走。1.1核心接口核心接口就这些可以发现跟之前的STL少了很多接口函数说明接口说明stack()构造空的栈empty()检测stack是否为空size()返回stack中元素的个数top()返回栈顶元素的引用push()将元素val压入stack中pop()将stack中尾部的元素弹出现在来练习一下1.最小栈最小栈我们可以写两个栈一个栈用来存最小的另外一个栈来放如果大于这个最小值入到另外那个栈中如果小于则插入到最小值存的那个栈中如果相等也插入最小值存的栈中写两个栈因为是STL中的所以可以不写构造系统会默认调用可以发现这个就不同于之前C中写的直接调用即可class MinStack { public: MinStack() { } void push(int val) { _st.push(val); if(_minst.empty() || val _minst.top()) { _minst.push(val); } } void pop() { if(_st.top() _minst.top()) { _minst.pop(); } _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } private: stackint _st; stackint _minst; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj new MinStack(); * obj-push(val); * obj-pop(); * int param_3 obj-top(); * int param_4 obj-getMin(); */2.栈的压入和弹出序列栈的压入和弹出序列入栈序列模拟出栈序列过程1.入栈序列入栈一个值2.栈顶数据跟出栈序列是否匹配持续出入栈序列结束就结束了class Solution { public: bool IsPopOrder(vectorint pushV, vectorint popV) { size_t popi0; stackint st; for(auto e : pushV) { //入栈 st.push(e); //跟出栈序列匹配 while(!st.empty() st.top() popV[popi]) { st.pop(); popi; } } return st.empty(); } };2.queuequeue队列先进先出FIFOFirst In First Out。最先进入的元素最先弹出就像排队买票先到的人先得到服务。2.1核心接口这些接口跟之前用法类似因此这两个的接口不用过多赘述。函数声明接口说明queue()构造空的队列empty()检测队列是否为空是返回true否则返回falsesize()返回队列中有效元素的个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素val入队列pop()将队头元素出队列1.二叉树的层序遍历二叉树的层序遍历方法一弄两个队列一个记录当前层数一个记录当前的那个值下到下一层就是把上一层的孩子入进去方法二用一个队列一层一层出加一个levelSize来控制levelSize代表当前层数据的个数 while(levelSize--)一层出完之后队列size就是下一层的数据个数用这个来更新levelSize即可class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint vv; queueTreeNode* q; int levelSize 0;//当前层数数据个数控制一层一层出 if(root) { q.push(root); levelSize 1; } while(!q.empty()) { //当前层数数据个数控制一层一层出 vectorint v; while(levelSize--) { TreeNode* front q.front(); q.pop(); v.push_back(front-val); if(front-left) q.push(front-left); if(front-right) q.push(front-right); } vv.push_back(v); //当前层出完下一层都进队列了队列的size就是下一层的数据个数 levelSizeq.size(); } return vv; } };3.容器适配器适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设 计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。STL标准库中stack和queue的底层结构 虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为 容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认 使用deque比如4.vector和list的优缺点vector优点1.尾插尾删效率不错,支持高效下标随机访问2.物理空间连续,所以高速缓存利用率高缺点:1.空间需要扩容,扩容有一些代价效率和空间浪费)2.头部和中间插入删除效率低list优点:1.按需申请释放空间,不需要扩容2.任意位置插入删除缺点:1.不支持下标随机访问5.deque可以说是vector和list的缝合既支持下标的随机访问又支持头尾的插入删除5.1用中控数组---指针数据来控制deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端 进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与 list比较空间利用率比较高。deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个 动态的二维数组双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问 的假象落在了deque的迭代器身上因此deque的迭代器设计就比较复杂5.2deque的缺陷与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是比vector高的。与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。5.3为什么选择deque作为stack和queue的底层默认容器stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性 结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据 结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如 list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为1. stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。2. 在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的 元素增长时deque不仅效率高而且内存使用率高。结合了deque的优点而完美的避开了其缺陷。6.priority_queue1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素 中最大的。2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的 顶部。4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作empty()检测容器是否为空size()返回容器中有效元素个数front()返回容器中第一个元素的引用push_back()在容器尾部插入元素pop_back()删除容器尾部元素5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。优先级队列并不保证内部已经完全排好序。它只保证堆性质heap property最大堆的根节点是最大值最小堆的根节点是最小值并且任何子树都满足这个性质。但除了根节点外其他元素的相对顺序是不确定的不一定是从大到小或从小到大排列。6.1核心接口优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中 元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用 priority_queue。注意默认情况下priority_queue是大堆。函数声明接口说明priority_queue()/priority_queue(first,last)构造一个空的优先级队列empty()检测优先级队列是否为空是返回true否 则返回falsetop()返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素7.简单模拟实现1.stackStack.h#pragma once namespace bit { //用Container适配转换出stack templateclass T,class ContainervectorT class stack { public: void push(const T x) { _con.push_back(x); } void pop() { _con.pop_back(); } T back() { return _con.back(); } T top() { return _con.back(); } const T top()const { return _con.back(); } size_t size()const { return _con.size(); } bool empty()const { return _con.empty(); } private: Container _con; }; }Test.cpp#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includevector #includelist using namespace std; #includeStack.h int main() { bit::stackint st; st.push(1); st.push(2); st.push(3); st.push(4); cout st.top() endl; st.pop(); return 0; }2.queueQueue.h#pragma once #includedeque namespace bit { //用Container适配转换出queue templateclass T, class Container listT class queue { public: void push(const T x) { _con.push_back(x); } void pop() { _con.pop_front(); } const T front() const { return _con.front(); } const T back() const { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }Test.cpp#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includelist using namespace std; #includeQueue.h int main() { bit::queueint, listint q; q.push(1); q.push(2); q.push(3); q.push(4); cout q.front() endl; q.pop(); return 0; }3.priority_queuePriorityQueue.h#pragma once #includevector templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } }; templateclass T class Greater { public: bool operator()(const T x, const T y) { return x y; } }; namespace bit { // 默认是大堆 templateclass T, class Container vectorT, class Compare LessT class priority_queue { public: void AdjustUp(int child) { Compare com; int parent (child - 1) / 2; while (child 0) { //if (_con[parent] _con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void push(const T x) { _con.push_back(x); AdjustUp(_con.size() - 1); } void AdjustDown(int parent) { // 先假设左孩子小 size_t child parent * 2 1; Compare com; while (child _con.size()) // child n说明孩子不存在调整到叶子了 { // 找出小的那个孩子 //if (child 1 _con.size() _con[child] _con[child 1]) if (child 1 _con.size() com(_con[child], _con[child 1])) { child; } //if (_con[parent] _con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent child; child parent * 2 1; } else { break; } } } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } const T top() { return _con[0]; } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }Test.cpp#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream using namespace std; #includePriorityQueue.h int main() { //priority_queueint pq;//大堆 bit::priority_queueint, vectorint, Greaterint pq;//小堆 //bit::priority_queueint pq;//大堆 pq.push(4); pq.push(1); pq.push(5); pq.push(7); pq.push(9); while (!pq.empty()) { cout pq.top() ; pq.pop(); } cout endl; return 0; }8.仿函数仿函数是一个类比如上面的priority_queue就是用了仿函数重载了operator()支持两个T的比较// 仿函数本质是一个类这个类重载operator(),他的对象可以像函数一样使用 templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } }; templateclass T class Greater { public: bool operator()(const T x, const T y) { return x y; } }; // 升序 // 降序 templateclass Compare void BubbleSort(int* a, int n, Compare com) { for (int j 0; j n; j) { // 单趟 int flag 0; for (int i 1; i n - j; i) { //if (a[i] a[i - 1]) if (com(a[i], a[i - 1])) { swap(a[i - 1], a[i]); flag 1; } } if (flag 0) { break; } } }int main() { Lessint LessFunc; Greaterint GreaterFunc; // 函数对象 cout LessFunc(1, 2) endl; cout LessFunc.operator()(1, 2) endl; //有名对象 int a[] { 9,1,2,5,7,4,6,3 }; BubbleSort(a, 8, LessFunc); BubbleSort(a, 8, GreaterFunc); //匿名对象 BubbleSort(a, 8, Lessint()); BubbleSort(a, 8, Greaterint()); return 0; }Less和Greater重载了operator()使得它们的对象可以像函数一样被调用这种技术称为仿函数Function Object或函数对象。它的好处是可以将比较行为作为参数传递给算法例如上面的BubbleSort。比函数指针更灵活可以在编译期内联展开性能更好。BubbleSort是一个函数模板它的第三个参数com是一个Compare 类型的对象也就是Lessint或Greaterint的实例。当在排序内部执行if (com(a[i], a[i-1]))时实际上会调用传入对象的operator()。如果传入LessFunc则com(a[i], a[i-1])等价于a[i] a[i-1]→升序排序。如果传入GreaterFunc则等价于a[i] a[i-1]→降序排序。需要自己实现仿函数1.类类型不支持比较大小比如你定义了一个Point类没有重载和那么直接写p1 p2会编译报错。→ 可以写一个仿函数内部按x坐标或到原点距离来比较。2.支持比较大小但是比较的逻辑不是想要的比如string类默认按字典序比较但你想按长度比较。→ 写一个CompareByLength仿函数。3.需要带状态的比较/操作仿函数可以拥有成员变量比如记录比较次数、设置阈值等普通函数做不到。4.需要多种不同的操作比如transform算法中可以传入一个“平方”仿函数、一个“取绝对值”仿函数等而不只是比较。今天的学习就到此结束期待我们的下一次再见