【C++第十课 - stack_queue】stack、queue的使用、适配器模型stack、queue和priority_queue的底层实现、deque

一、stack使用

stack是个容器适配器
stack想要访问里面所有的数据必须pop和top，不能使用范围for

1、push

插入向量

	stack<int> 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:stack<int> _st;stack<int> _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(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> 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
中缀表达式
所有的符号都是在要运算的操作数字的中间出现。例如（a+b+cd）/e
后缀表达式（逆波兰）
所有的符号都是在要运算的操作数字的后面出现。例如 abcd*++e/

二、queue的使用

容器container默认是deque(双端队列)

priority_queue

不是先进先出，是按优先级出
底层是：堆
是适配器，不是容器了
compare是比较的函数

习题

方法一

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;queue<int> qlayer;vector<vector<int>> vv;int layer = 1;if(root){q.push(root);qlayer.push(layer);}while(!q.empty()){vector<int> 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)

	template<class T, class Container = deque<T>>class 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的底层实现

	template<class T, class Container = deque<T>>class 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的底层实现

是优先级队列，优先级高的先出，因此用堆进行实现

	template<class T, class Container = vector<T>>class 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
{template<class T>class less{public:bool operator()(T x, T y){return x < y;}};template<class T>class greater{public:bool operator()(T x, T y){return x > y;}};template<class T, class Container = vector<T>, class Compare = greater<T>>class 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