I.前言本章我们来探讨stackqueue以及priority_queue的使用以及实现II.Stack类0x00 stack介绍栈Stack是一种特殊的数据结构也是一种容器适配器主要特点是先进后出LIFO进行插入和删除的一端叫做栈顶另一端为栈底。 栈在原则上不允许进行中部和底部的操作这样会破坏栈结构的完整性栈是遍历不是由迭代器来实现的栈Stack是作为容器适配器被实现的容器适配器是对特定类封装作为其底层容器并提供一组特定的成员函数来访问其元素将特定类作为其底层如图所示我们可以看到栈有两个模板参数参数1T栈中的元素类型同时也是底层容器中的元素类型参数2Container实现栈时用到的底层容器这里为缺省参数缺省结构为双端队列deque也就是说Stack的底层容器可以是任何标准的容器类模板或者一些特定的容器类这些容器应该支持一下操作empty判空操作back获取尾部元素操作push_back尾部插入元素操作pop_back尾部删除元素操作0x01 Stack使用函数说明接口说明Stack()构造空栈empty()检测Stack是否为空size()返回Stack中元素个数top()返回栈顶元素push()压栈pop()出栈#include iostream #include stack using namespace std; void test_stack() { /* 创建一个存储整型的栈 */ stackint st; /* 入栈 */ st.push(1); st.push(2); st.push(3); st.push(4); /* 打印栈 */ while (!st.empty()) { // 如果栈不为空则进入循环 cout st.top() ; // 打印栈顶元素 st.pop(); // 出栈 } cout endl; }III. queue类0x01 队列介绍队列queue是一种特殊的数结构同时也是一种容器适配器遵循先进先出FIFO原则其中从容器一端插入元素另一端提取元素。队列在原则上 是不允许进行 中部的操作这样会破坏队列的完整性。队列queue也是作为容器适配器被实现的容器适配器是对特定类封装作为其底层容器并提供一组特定的成员函数来访问其元素将特定类作为其底层。元素从队尾入列队头出列可以看出队列也有两个模板参数参数1T栈中的元素类型同时也是底层容器的元素类型参数2Container实现栈是用到的底层容器这里为缺省参数缺省结构为双端队列 dequequeue的底层容器可以是任何标准的容器类模板或i这一些其特定的容器类empty检查队列是否为空size返回队列中的有效元素个数front返回队头元素的引用back返回队尾元素的引用psuh_back在队列尾部入队列pop_front在队列头部出队列0x02 queue使用函数声明接口说明queue()构造空的队列empty()检测队列是否为空size()返回队列中的元素个数back()返回队尾元素front()返回队头元素push()入队pop()出队#include iostream #include queue using namespace std; void test_queue() { /* 创建一个存储整型的队列 */ queueint Q; /* 入队 */ Q.push(1); Q.push(2); Q.push(3); Q.push(4); /* 打印队列 */ while (!Q.empty()) { // 如果队列不为空则进入循环 cout Q.front() ; // 打印队头元素 Q.pop(); // 出队 } cout endl; }IV.适配器从应用角度来看STL中的适配器分为三类容器适配器container adapters迭代器适配器iterator adapters仿函数适配器functor adapters其中容器适配器可修改底层为指定容器如由vector构成的栈、由list构成的队列迭代器适配器可以实现其他容器的反向迭代器后续介绍最后的仿函数适配器就厉害了几乎可以无限制的创造出各种可能的表达式V.Stack和queue的底层结构虽然 【stack】和 【queue】中也可以存放元素但是在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为【stack】和 【queue】只是对其它容器的接口进行了包装STL 中【queue】和 【stack】默认使用 【deque】比如注意容器支持 迭代器但是容器适配器不支持迭代器因为栈和队列这种数据结构不能随便去遍历不然会导致发生变化不易维护VI.deque 原理介绍双端队列 deque是一种双开口“连续“空间的数据结构双开口的含义可以在队尾端进行插入和删除的操作且时间复杂度为O1与vector相比头插效率高不需要移动元素与list相比空间利用率比较高0x01 deque的底层结构deque的底层结构通常是由多个固定大小的缓冲区组成每个缓冲区是一个连续的存储块。这些缓冲区通过一个指向前一个缓冲区和一个指向后一个缓冲区的指针进行连接形成一个双向链表deque的双向链表由一个或多个缓冲区组成每个缓冲区都包含一个指向前一个缓冲区和一个指向后一个缓冲区的指针。第一个缓冲区的指向前一个缓冲区的指针为空指针最后一个缓冲区的指向后一个缓冲区的指针也为空指针。当需要在deque的头部或尾部插入或删除元素时只涉及到相关缓冲区的操作而不会涉及其他缓冲区。这种设计使得deque的插入和删除操作时间复杂度为常数级别O(1)。我们需要了解的是如果在队列头部插入元素首先插入的是现在7占据的位置而在队尾插入会先占据16的位置里面会有一个代码为cur-firststart是为了确定插入的相对位置0x02 deque的缺陷维度优点缺点两端操 作效率极高头部 / 尾部添加、删除元素appendleft/popleft/append/pop均为O(1)时间复杂度不支持高效的中间元素操作中间插入 / 删除为O(n)时间复杂度内存与扩容基于链表结构实现无需预先分配固定内存动态扩容无性能损耗内存占用略高于列表元素存储不连续内存局部性差随机访问支持通过索引访问元素dq[i]基础查询可用随机访问效率远低于列表为O(n)时间复杂度功能特性内置线程安全、旋转操作rotate、长度限制maxlen适合队列 / 栈场景功能聚焦于双端操作不支持切片等列表的灵活便捷操作适用场景高频两端增删、线程间数据通信、固定长度缓存、滑动窗口需要大量随机访问、中间增删、切片处理的场景❓ 那什么场景适合用 deque 呢虽然不够极致但是还是有用武之地的大量头尾插入删除偶尔随机访问的情况可以使用 deque。0x03 dequestack 和 queue 的底层默认容器❓ 思考为什么选择 deque 作为 stack 和 queue 的底层默认容器① stack 是一种后进先出的特殊线性数据结构因此只要具有push_back() 和 pop_back()操作的线性结构都可以作为 stack 的底层容器比如 vector 和 list 都可以② queue 是先进先出的特殊线性数据结构只要具有push_back() 和 pop_front()操作的线性结构都可以作为 queue 的底层容器比如 list但 STL 最终选择用 deque 作为 stack 和 queue 的底层容器其主要原因是如下stack 和 queue不需要遍历因此 stack 和 queue 没有迭代器只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高扩容时不需要搬移大量数据queue中的元素增长时deque 不仅效率高而且内存使用率高。 结合了deque的优点而完美的避开了其缺陷。#includeiostream namespace zzz { templateclass T,class Container dequeT class Queue { public: //入队 void push(const T x) { _con.push_back(x); } //出队 void pop() { _con.pop_front(); } //获取队头元素 T front() { return _con.front(); } const T front()const { return _con.front(); } //获取队尾元素 T back() { return _con.back(); } const T back() const { return _con.back(); } //获取队列中有效元素个数 size_t size() const { return _con.size(); } //判空 bool empty() const { return _con.size() 0; } //交换元素 void swap(QueueT, Container q) { _con.swap(q._con); } private: Container _con; }; }#includeiostream namespace zzz { templateclass T,class Container dequeT class Stack { public: //入栈 void push(const T x) { _con.push_back(x); } //出栈 void pop() { _con.pop_back(); } //活取栈顶元素 T top() { return _con.back(); } const T top() const { retunr _con.back(); } //获取有效元素个数 size_t size() const { return _con.size(); } //判空 bool empty() const { reutrn _con.empty(); } //交换元素 void swap(StackT, Container st) { _con.swap(st._con); } private: Container _con; }; }VII.优先级队列0x00 介绍优先级队列priority_queue是容器适配器的一种常用来进行队数据的优先级处理比如优先级高的值在前面这其实就是数据结构的堆它俩本质上是i相同的底层都是以数组存储的完全二叉树不过优先级队列priority_queue中 加入泛型编程的思想且属于STL中的一部分priority_queue是C标准库中的一个容器适配器container adapter用于实现优先队列priority queue的数据结构。优先队列是一种特殊的队列其中的元素按照一定的优先级进行排序每次取出的元素都是优先级最高的。它的底层实现通常使用堆heap数据结构。在C中priority_queue模板类定义在queue头文件中可以通过指定元素类型和比较函数来创建不同类型的优先队列。比较函数用于确定元素的优先级可以是函数指针、函数对象或Lambda表达式。priority_queue被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类。元素从特定容器的”尾部“弹出其称为优先级队列的顶部0x01 区分 优先级队列 和 队列队列是一种先进先出FIFO的数据类型每次元素的入队都只能在队尾操作出队在队头操作优先级队列并不满足先进先出的条件它更像是数据类型的堆优先级队列每次出队的元素是队列中优先级最高的元素而不是队头元素。这个优先级可以通过元素的大小进行定义。0x02 priority_queue 构造优先级队列默认使用vector作为底层存储数据的容器在 vector 上又使用了 堆算法 将 vector 中的元素构造成堆的结构因此priority_queue 就是 ---- 堆所以在需要用到 堆 的地方都可以考虑使用 priority_queue0x03 priority_queue 常用接口VIII.模拟实现priority_queue据我所知在优先级队列中插入数据和删除数据的时间复杂度 为 。默认情况下的优先级队列是大堆我们先不考虑用仿函数去实现兼容大堆小队排列问题我们先去实现大堆先把基本的功能实现好带着讲解完仿函数后再去进行优化实现优先级队列相较于普通的队列其区别主要是在 push 和 pop 上即需要在插入 / 删除数据的同时增添调整的功能并且 STL 的优先级队列是由堆来维护的void push(const T x) { _con.push_back(x); AdjustUp(_con.size() - 1); }入队时将数据推入后从最后一个元素开始进行上调。出队时采用堆的删除手法将根元素即队头和最后一个元素进行交换并调用尾删掉队头。既然用了头尾交换法我们就不得不对队列重新调整所以从根位置进行下调即可完成出队。void pop() { assert(!_con.empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); }既然需要上调和下调操作我们不可避免地需要实现上调和下调的算法。我们这里暂时写死设计成大堆的 AdjustUp 和 AdjustDown#includeiostream /*向上调整算法*/ void AdjustUp(size_t child) { size_t parent (child - 1) / 2; while (child 0) { if (_con[parent] _con[child]) { swap(_con[parent], _con[child]); child parent; parent (child - 1) / 2; } else { break; } } } /*向下调整算法*/ void AdjustDown(size_t parent) { size_t child parent * 2 1; while (child _con.size()) { if (child 1 n _con[child] _con[child 1]) { child; } if (_con[parent] _con[child]) { swap(_con[parent], _con[child]); parent child; child parent * 2 1; } else { break; } } }我们把_con转换的接口实现一下const T top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); }0x01 仿函数我们先来看我们写的大堆优先级队列code#include iostream #include vector #include assert.h using namespace std; namespace foxny { templateclass T, class Container vectorT class priority_queue { public: /* 向上调整算法 */ void AdjustUp(size_t child) { size_t father (child - 1) / 2; while (child 0) { if (_con[father] _con[child]) { swap(_con[father], _con[child]); child father; father (child - 1) / 2; } else { break; } } } /* 向下调整算法 */ void AdjustDown(size_t father) { size_t child father * 2 1; // 默认认为左孩子大 while (child _con.size()) { // 判断右孩子是否存在并且是否比左孩子大 if (child 1 _con.size() _con[child] _con[child 1]) { child 1; } if (_con[father] _con[child]) { swap(_con[father], _con[child]); father child; child father * 2 1; } else { break; } } } /* 入数据 */ void push(const T x) { _con.push_back(x); AdjustUp(_con.size() - 1); } /* 出数据 */ void pop() { assert(!_con.empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } /* 返回堆顶数据 */ const T top() { return _con[0]; } /* 返回大小 */ size_t size() { return _con.size(); } /* 判断是否为空 */ bool empty() { return _con.empty(); } private: Container _con; }; }我们发现的问题是——如果之后想按升序排列就没办法用这个代码实现了我们这里写的是排降序的大堆排升序的话需要再写一个小堆C 在这里有一种叫仿函数的东西可以控制这些东西我们下面先来介绍一下仿函数概念使一个类的使用看上去像一个函数。可以像函数一样使用的对象称为函数对象其实现就是在类中重载operator()使得该类具备类似函数的行为就是一个仿函数类了。先来看一个最简单的仿函数struct less { //仿函数函数对象——对象可以像调用函数一样去使用 bool operator()(int x,int y) { return xy; } }; void test_functor() { less lessCmp; cout lessCmp(10,20) endl; }我们还可以使其能够支持泛型我们加一个 template 模板:// 支持泛型 templateclass T struct less { bool operator()(const T x, const T y) const { return x y; } }; void test_functor() { lessint lessCmp; cout lessCmp(10, 20) endl; }less 是用来比较谁小的对应的我们再实现一个比较谁大的 greater// less: 小于的比较 templateclass T struct less { bool operator()(const T x, const T y) const { return x y; } }; // greater: 大于的比较 templateclass T struct greater { bool operator()(const T x, const T y) const { return x y; } }; void test_functor() { lessint lessCmp; cout lessCmp(10, 20) endl; greaterint GreaterCmp; cout GreaterCmp(10, 20) endl; }0x02加入仿函数后的priority_queue我们现在用仿函数去比较那些数据这样就不会写死了#include iostream #include vector #include functional // 这里放的是一些仿函数 #include assert.h using namespace std; namespace foxny { // less: 小于的比较 templateclass T struct less { bool operator()(const T x, const T y) const { return x y; } }; // greater: 大于的比较 templateclass T struct greater { bool operator()(const T x, const T y) const { return x y; } }; templateclass T, class Container vectorT, class Compare lessT class priority_queue { public: /* 向上调整算法 */ void AdjustUp(size_t child) { Compare cmpFunc; size_t father (child - 1) / 2; while (child 0) { // if (_con[father] _con[child]) { if (cmpFunc(_con[father], _con[child])) { swap(_con[father], _con[child]); child father; father (child - 1) / 2; } else { break; } } } /* 向下调整算法 */ void AdjustDown(size_t father) { Compare cmpFunc; size_t child father * 2 1; // 默认认为左孩子大 while (child _con.size()) { // if (child 1 _con.size() _con[child] _con[child 1]) { if (child 1 _con.size() cmpFunc(_con[child], _con[child 1])) { child 1; } // if (_con[father] _con[child]) { if (cmpFunc(_con[father], _con[child])) { swap(_con[father], _con[child]); father child; child father * 2 1; } else { break; } } } /* 入数据 */ void push(const T x) { _con.push_back(x); AdjustUp(_con.size() - 1); } /* 出数据 */ void pop() { assert(!_con.empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } /* 返回堆顶数据 */ const T top() { return _con[0]; } /* 返回大小 */ size_t size() { return _con.size(); } /* 判断是否为空 */ bool empty() { return _con.empty(); } private: Container _con; }; } // 大于比较搞小堆 void test_priority_queue2() { priority_queueint, vectorint, greaterint pQ; pQ.push(2); pQ.push(5); pQ.push(1); pQ.push(6); pQ.push(8); while (!pQ.empty()) { cout pQ.top() ; pQ.pop(); } cout endl; } // 小于比较搞大堆 void test_priority_queue1() { priority_queueint pQ; pQ.push(2); pQ.push(5); pQ.push(1); pQ.push(6); pQ.push(8); while (!pQ.empty()) { cout pQ.top() ; pQ.pop(); } cout endl; }0x03 迭代器实现// 创造空的优先级队列 priority_queue() : _con() {} // 迭代器 templateclass InputIterator priority_queue (InputIterator first, InputIterator last) : _con(first, last) { while (first ! last) { _con.push_back(*first); } for (int father (_con.size()-1-1) / 2; father 0; father) { AdjustDown(father); } }IX priority_queue面试题优先级队列堆可以用来进行排序和解决Top-K问题比如查找第 k 个最大的值就比较适合使用优先级队列思路利用数组建立大堆数组从大到小排序删除前K-1个元素选出队头即可class Solution { public: int findKthLargest(vectorint nums, int k) { // 将数组中的元素 放入 优先级队列--堆 priority_queueint p(nums.begin(),nums.end()); // 将优先级队列 中的前K-1 个元素删除掉 for(int i 0;i k-1;i) { p.pop(); } return p.top(); } };