目录前言1 stack的介绍和使用1.1 stack的介绍​编辑1.2stack的使用2 queue的介绍和使用2.1 queue的介绍2.2 queue的使用​编辑3 priority_queue的介绍和使用3.1 priority_queue的介绍3.2 priority_queue的使用4 容器的适配器4.1 什么是适配器4.2 STL标准库中stack和queue的底层结构4.3 deque的简单介绍4.3.1 deque的原理介绍4.3.2 deque的缺点4.4 为什么选择deque作为stack和queue的底层默认容器4.5 stack的模拟实现代码如下注意按需实例化4.6 queue的模拟实现代码如下4.7 priority_queue的模拟实现(没有虚函数基础部分)push向上调整的代码如下push代码如下:pop向下调整的代码如下pop代码如下topsizeempty仿函数仿函数改良的priority_queue代码如下练习结语前言在 C STL 中stack、queue、priority_queue都属于容器适配器。适配器本身不存储真实数据它不直接实现容器底层内存而是对已有容器deque、vector、list 等进行封装对外提供一套全新的接口改变原有容器的行为语义。stack遵循LIFO 后进先出只允许在容器同一端完成插入与删除 queue遵循FIFO 先进先出从尾部入队、头部出队 priority_queue为优先级队列内部对元素做堆排序每次取出优先级最高的元素。本篇文档将分别讲解三种适配器的接口使用、底层实现、底层容器要求同时模拟实现简易版stack、queue加深对容器适配器的理解。1 stack的介绍和使用1.1 stack的介绍stack是一个适配器后进先出结构如下图1.2stack的使用重点易错点pop()只删除不返回栈顶值要取值先top()再pop()对空栈调用top()/pop()程序直接未定义行为崩溃操作前必须用empty()判断。2 queue的介绍和使用2.1 queue的介绍queue也是一个适配器先进先出结构如下图2.2 queue的使用3 priority_queue的介绍和使用3.1 priority_queue的介绍priority是优先的意思priority_queue的意思是优先队列。它的接口与stack的接口类似3.2 priority_queue的使用push就是正常压入进去这里最需要注意的是pop和top它要选择优先级高的进行pop和toppriority_queue默认情况下是大的优先级高 默认是大堆如果想控制小的优先级高就得用到一个叫仿函数的东西。priority_queue的底层就是我们之前的堆堆的底层就是数组用来表示完全二叉树所以priority_queue的默认适配容器是vector。4 容器的适配器4.1 什么是适配器适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。相当于一个转接的接口。4.2 STL标准库中stack和queue的底层结构虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和队列只是对其他容器的接口进行了包装STL中stack和queue默认使用deque比如下图的Container是容器的意思目的是使用这个容器来完成我需要的接口。4.3 deque的简单介绍deque虽然叫双端队列但其实deque跟queue没有关系队列要求先进先出deque不要求先进先出我们可以把deque当成vector和list的缝合怪。4.3.1 deque的原理介绍deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。因为vector与list的优缺点过于明显这是为什么产生deque的原因。从上图可以看出deque使用的是随机迭代器 我们从这就可以看出deque是个缝合怪既支持下标访问又支持头插头删相当于list与vector的结合体。我们先回顾一下list与vector的结构vector是一段连续的空间list是一个一个节点作为空间也就是很多小空间然后通过指针连接在一起。deque为了解决vector频繁扩容的问题采取的操作是开辟一块连续空间如果连续空间满了就开辟下一块同样大小的空间不扩容直接开辟新空间也就是这样。这些空间连接deque是运用中控数组来实现就是deque有一个中控数组中控数组里面存的是指针指向的就是对应空间然后一开始的空间都会尽量往中控数组的中间位置靠如下图头插与尾插如下图当然这个也会要扩容只是不会像vector一样拷贝的那么多如果中控数组满了就会扩容出一个更大的中控数组然后把指针拷贝过去。双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示deque的迭代器里面有四个成员firstlast指向buf空间的开始和结束cur指向的是想要访问的数据node 指向的是中控数组当前指向该buf空间的指针的位置用图表示的话就是如下图4.3.2 deque的缺点与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。4.4 为什么选择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的优点而完美的避开了其缺陷templateclass T, class Container dequeT class stack { public : stack() {} void push(const T x) { _con.push_back(x); } void pop() { _con.pop_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; };4.5 stack的模拟实现stack非常简单接口一样简单如下图代码如下#pragma once namespace wxd { templateclass T, class containervectorT class my_stack { public: void push(const T value) { _con.push_back(value); } void pop() { _con.pop_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; }; }但我们学完适配器后其实完全不用这么写因为stack这个东西完全可以用vector来进行封装转换因为栈主要支持的就三个东西一个入栈一个出栈一个查询栈顶元素那入栈不就对应vector的尾插出栈不就对应vector的尾删查询栈顶元素不就是查询vector内部最后一个元素注意按需实例化请观看下面的代码#pragma once namespace wxd { templateclass T, class containervectorT class my_stack { public: void push(const T value) { _con.push_back(value); } void pop() { _con.pop_front(); } 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; }; }#includeiostream #includevector #includelist using namespace std; #includestack.h #includePriorityQueue.h #includequeue.h #includemy_stack.h int main() { //w::stackint, vectorint st; wxd::my_stackint st; st.push(1); st.push(2); st.push(3); st.push(4); cout st.size() endl; return 0; }我使用的pop是pop_front这个接口在vector中是不存在的但是编译器没有报错这是为什么因为我们没有调用pop这个接口没调用的函数编译器不会实例化只会检查大体有没有问题。所以有的时候模板实现一直没问题突然有一次调用出问题了很可能就是这个接口之前一直没有使用过然后这个接口内部有点问题所以写完代码与接口时需要及时检查与调用。4.6 queue的模拟实现queue的实现是非常简单的与stack类似它的接口是非常简单的如下代码如下#pragma once #includedeque namespace wxd { templateclass T,class container dequeT class my_queue { public: void push(const T value) { _con.push_back(value); } void pop() { _con.pop_front(); } T back() { return _con.back(); } T front() { return _con.front(); } const T back()const { return _con.back(); } const T front()const { return _con.front(); } size_t size()const { return _con.size(); } bool empty()const { return _con.empty(); } private: container _con; }; }需要注意的是队列而言就不能用vector了因为队列是一端进一端出如果用vector出队列的时间复杂度是ON了。我们如果用vector来作为Container一开始不会报错直到我们调用pop才会报错因为vector是没有pop_front这个操作的这也体现了 前面我们所讲的按需实例化问题。4.7 priority_queue的模拟实现(没有虚函数基础部分)在模拟实现前我们应该回顾一下二叉树了解一下parent与child的关系关系如下parent(child-1)/2;left_childparent*21;right_childparent*22;我们在使用priority_queue的时候将其看作一个完全二叉树然后进行操作。push如上图我们将数据插入进去需要对这个完全二叉树进行向上调整不然无法实现priority_queue的接口它的接口会产生错误。向上调整的代码如下//建堆 向上调整 void AdjustUp(int child) { size_t parent (child - 1) / 2; while (child 0) { if (_con[child] _con[parent]) { swap(_con[child], _con[parent]); child parent; parent (child-1)/2; } else { break; } } }如果这个二叉树中没有元素上面代码也相当于建堆。我们进行push完就要调用上面的AdjustUp进行建堆或者向上调整不然调用top接口或者调用pop接口会出现错误的值。push代码如下:void push(const T x) { _con.push_back(x); return AdjustUp(_con.size() - 1); }pop删除必须要把堆顶元素和最后一个元素交换然后对vector——pop_back随后再对堆顶元素向下调整重新调整为堆结构 如果直接将顶部元素删除二叉树的parent与child的关系会发生大变化兄弟变父子叔侄变兄弟。向下调整的代码如下//向下调整 void AdjustDown(int parent) { size_t child parent * 2 1; while (child _con.size()) { if (child 1 _con.size() _con[child 1] _con[child])child; if (_con[child] _con[parent]) { swap(_con[child], _con[parent]); parent child; child parent * 2 1; } else { break; } } }pop代码如下void pop() { //防止关系混乱所以需要删除的数与尾部的数交换 swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); }topconst T top() { return _con[0]; }sizesize_t size()const { return _con.size(); }emptybool empty()const { return _con.empty(); }仿函数首先仿函数是一个类这个类里面有()运算符重载函数调用运算符重载为什么叫仿函数因为它使用起来像函数长得与函数很像。如下图这是一个基础的仿函数#include iostream // 仿函数类 struct Add { int operator()(int a, int b) { return a b; } }; int main() { Add f; // f是对象但像函数一样调用这就是仿函数 std::cout f(3,5); //输出8 return 0; }类内如果没有成员变量的时候类的大小为1仿函数就普遍是这种情况因为一般仿函数对应的类的内部基本就是只有一个operator()的重载。仿函数改良的priority_queue代码如下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; }; }练习102. 二叉树的层序遍历 - 力扣LeetCodeclass Solution { public: vectorvectorint levelOrder(TreeNode* root) { vector vector int ret; if (!root) { return ret; } queue TreeNode* q; q.push(root); while (!q.empty()) { int currentLevelSize q.size(); ret.push_back(vector int ()); for (int i 1; i currentLevelSize; i) { auto node q.front(); q.pop(); ret.back().push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return ret; } }; 作者力扣官方题解 链接https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/241885/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。155. 最小栈 - 力扣LeetCodeclass MinStack { public: void push(int value) { _st.push(value); if(minst.empty()||valueminst.top())minst.push(value); } 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(value); * obj-pop(); * int param_3 obj-top(); * int param_4 obj-getMin(); */栈的压入、弹出序列_牛客题霸_牛客网class Solution { public: /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param pushV int整型vector * param popV int整型vector * return bool布尔型 */ bool IsPopOrder(vectorint pushV, vectorint popV) { // write code here stackint_st; size_t i0; for (auto e : pushV) { _st.push(e); while(!_st.empty()_st.top()popV[i]){ _st.pop(); i; } } return _st.empty(); } };结语谢谢你的观看希望可以给你提供帮助