安徽省建设厅网站域名,最近发生的新闻热点事件,大数据,精美图片做网站上哪儿去找图目录 一、stack使用1、push2、pop3、empty4、top题目1、最小栈2、栈的压入、弹出序3、逆波兰表达式求值 二、queue的使用priority_queue习题 三、适配器stack的底层实现queue的底层实现priority_queue的底层实现仿函数/函数对象函数指针 四、deque 一、stack使用 stack是个容器… 目录 一、stack使用1、push2、pop3、empty4、top题目1、最小栈2、栈的压入、弹出序3、逆波兰表达式求值 二、queue的使用priority_queue习题 三、适配器stack的底层实现queue的底层实现priority_queue的底层实现仿函数/函数对象函数指针 四、deque 一、stack使用 stack是个容器适配器 stack想要访问里面所有的数据必须pop和top不能使用范围for 1、push
插入向量 stackint s;s.push(1);s.push(2);s.push(3);s.push(4);2、pop 移除栈顶数据 3、empty stack为空返回true stack非空返回false 4、top 取栈顶元素 题目
1、最小栈
https://leetcode.cn/problems/min-stack/ 双栈解决 方案一 设计两个stack一个stack存放数值另一个stack存放最小值 存了这么多5有点浪费空间 改进方案二 方案二 当_stpop的与_minst栈顶元素一样的时候_minst也pop 存在的问题当有好多个最小值是_minst要push进去多个-改进方案三 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;
};方案三
2、栈的压入、弹出序
用栈来模拟入栈和出栈过程 1如果pushV当前入栈的值和popV当前出栈的值一样pushV向后移一位popV向后移一位 2如果pushV当前入栈的值和popV当前出栈的值不一样分两种情况 第一种情况如果栈顶元素与popV当前出栈元素一样popv向后移一位栈顶元素弹出 第二种情况如果栈为空或栈顶元素与popV当前的出栈元素不一样将pushV当前入栈元素压入栈中pushV向后移一位 之后开始对栈中元素按照popV的顺序进行出栈如果对不上就是False 简化先入栈再判断 1、入栈序列当前数据入栈 2、栈顶元素与出栈序列进行比较 1相等出栈出栈序列 2不相等 2的结束标志栈为空或不相等 所有的结束标志入栈序列走完 class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV) {// write code herestackint s;size_t pushi 0;size_t popi 0;while(pushi pushV.size()){s.push(pushV[pushi]);while(!s.empty() s.top() popV[popi]){s.pop();popi;}pushi;}return popi popV.size();}
};3、逆波兰表达式求值
逆波兰表达式求值 前缀表达式波兰 所有的符号都是在要运算的操作数字的前面出现。例如 /abcde 中缀表达式 所有的符号都是在要运算的操作数字的中间出现。例如abcd/e 后缀表达式逆波兰 所有的符号都是在要运算的操作数字的后面出现。例如 abcd*e/ 二、queue的使用 容器container默认是deque(双端队列) priority_queue 不是先进先出是按优先级出 底层是堆 是适配器不是容器了 compare是比较的函数 习题 方法一 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* q;queueint qlayer;vectorvectorint vv;int layer 1;if(root){q.push(root);qlayer.push(layer);}while(!q.empty()){vectorint v;while(qlayer.front() layer ){TreeNode* cur q.front();q.pop();v.push_back((*cur).val);if(cur-left){q.push(cur-left);qlayer.push(layer 1);}if(cur-right){q.push(cur-right);qlayer.push(layer 1);}qlayer.pop();}vv.push_back(v);layer;}return vv;}
};方法二
三、适配器 适配器就是一个设计模式 由容器string、vector、list、deque封装、转换而成的底层数据的管理不是由自己负责的 默认容器 stack - deque queue - deque priority_queue - vector stack的底层实现 站和队列的底层实现都是复用的容器(string、vector、list) templateclass T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};在这里插入代码片queue的底层实现 templateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}const T front(){return _con.front();}const T back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};priority_queue的底层实现 是优先级队列优先级高的先出因此用堆进行实现 templateclass T, class Container vectorTclass priority_queue{public:void adjust_up(){int child _con.size() - 1;int parent (child - 1) / 2;while (parent 0){if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void push(const T x){_con.push_back(x);adjust_up();}void adjust_down(){int parent 0;int left parent * 2 1; int right parent * 2 2;int size _con.size();while (left size){int big left;if (right size _con[right] _con[left]){big right;}if (_con[big] _con[parent]){swap(_con[big], _con[parent]);parent left;left parent * 2 1;right parent * 2 2;}else{break;}}}//优先出优先级高的void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down();}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};priority_queue里面用的仿函数–第三个模板参数
仿函数/函数对象 为了解决函数指针的缺陷 回调函数这个函数已经写好了在用到它的时候再去调它C语言用这个 Compare可以定义成成员对象也可以在用的时候创建一个Compare com; 模板参数传的是类型编译的时候传递 namespace zyh
{templateclass Tclass less{public:bool operator()(T x, T y){return x y;}};templateclass Tclass greater{public:bool operator()(T x, T y){return x y;}};templateclass T, class Container vectorT, class Compare greaterTclass priority_queue{public:void adjust_up(){int child _con.size() - 1;int parent (child - 1) / 2;while (parent 0){if (_com(_con[child], _con[parent])){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void push(const T x){_con.push_back(x);adjust_up();}void adjust_down(){int parent 0;int left parent * 2 1; int right parent * 2 2;int size _con.size();while (left size){int big left;if (right size _com(_con[right], _con[left])){big right;}if (_com(_con[big], _con[parent])){swap(_con[big], _con[parent]);parent left;left parent * 2 1;right parent * 2 2;}else{break;}}}//优先出优先级高的void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down();}const T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;Compare _com;};
}模板参数不仅能在类里面传递还能在函数里面传递 上面是类模板只能穿仿函数。如果传函数指针类里面也是将它转换成类型还是拿不到函数指针 下面是函数模板可以传仿函数对象、函数指针。能传函数指针是因为可以根据函数指针推出类型同时参数那也可以得到函数指针。 函数指针 传递的是对象是参数变量运行时传递的 四、deque
双端队列但不是队列。就像优先级队列也不是队列 拥有list和vector的所有功能尾插尾删、头插头删、[ ] [ ]的效率没有vector的高 vector 优点物理结构连续存储的优势 1下标随机访问 2缓存命中高 缺点 1前面插入删除效率低 2扩容有消耗 list 优点 1扩容没有消耗 2随机插入删除效率高 缺点 1不支持下标随机访问 2缓存命中低 deque 优势头插头删尾插尾删很不错 不足 随机访问效率没有vector高 访问第i个值【假设保持每个buff一样大都是10】 如果第一个buff不是从头开始的不在第一个buff那么i - 第一个buff的数据个数 第i/10个buff中 在这个buff的第i%10位置 中间插入删除如何实现 如果不需要保持每个buff一样大只能挪动数据 如果不需要保持每个buff一样大可以对当前buff扩容或者挪动数据 结论 1、小标随机访问效果不错但是跟vector仍有差距 2、中间插入删除效率差 如果一个适配器经常头插头删、尾插尾删 - deque 如果少量的下标访问 - 可以用deque 如果大量的下标访问 - 需要用vector 如果中间插入删除 - list
