stack

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

stack的使用(最常用的)：

习题练习

逆波兰表达式求值

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto str:tokens){if(str=="+"|| str=="-"|| str=="*"|| str=="/"){//出栈中操作数进行运算int right=st.top();st.pop();int left=st.top();st.pop();switch(str[0]){case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*':st.push(left*right);break;case '/':st.push(left/right);break;}}else{st.push(stoi(str));}}return st.top();}
};

基本计算器

class Solution {
public:int pre(char ch)//优先级判断{if(ch=='+'|| ch=='-')return 1;else if(ch=='(' || ch==')')return 3;else//如果有*/return 2;}int calculate(string s) {vector<int> v;stack<char> st;int i=0;for(int i=0;i<s.size();i++){if(isdigit(s[i]))//遇到操作数放到vector里{string s1;while(isdigit(s[i])){s1+=s[i++];}i--;v.push_back(stoi(s1));//如果遇到是-1if(v.size()==st.size()==1){v.pop_back();st.pop();v.push_back(-stoi(s1));}}else if(s[i]!=' ')//遇到操作符{if(s[i]=='('){//递归解决string tmp(s,i+1);v.push_back(calculate(tmp));//找到)i++;int count=1;//代表1个(,对应着一个),如果在找的过程中发现了第二个(,count++while(count!=0){if(s[i]=='('){count++;}else if(s[i]==')'){count--;}if(count!=0)i++;}//递归解决完之后，面临和上面遇到-1一样的情况if(v.size()==st.size()==1){int a=v.back();v.pop_back();st.pop();v.push_back(-a);}continue;}if(s[i]==')'){break;}while(!st.empty()){char top=st.top();//ch运算符优先级比top高，入栈if(pre(s[i])>pre(top)){st.push(s[i]);}else{_operator(st,v);}}if(st.empty()){st.push(s[i]);}}}while(!st.empty()){_operator(st,v);}return v.back();}void _operator(stack<char>& st,vector<int>& v)//出栈顶操作符对两个操作数运算然后将结果放回vector{char top=st.top();//出栈顶元素st.pop();int right=v.back();v.pop_back();int left=v.back();v.pop_back();//运算v中数据把结果放回去switch(top){case'+':v.push_back(left+right);break;case'-':v.push_back(left-right);break;}}};

stack模拟实现

namespace st
{template<class T,class Container = deque<T>>//不管Container这个底层容器是谁，都可以适配栈class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
};void test_stack()
{st::stack<int, vector<int>> v;v.push(1);v.push(3);v.push(2);v.push(7);v.push(5);while (!v.empty()){cout << v.top() << " ";v.pop();}cout << endl;
}int main()
{test_stack();return 0;
}

queue

队列是一种容器适配器，先进先出，其中从容器一端插入元素，另一端提取元素。

queue模拟实现

queue的接口中存在头删和尾插，因此使用vector来封装效率太低，可以借助list来模拟实现queue

namespace q
{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;};
};void test_queue()
{q::queue<int, list<int>> q;q.push(4);q.push(3);q.push(2);q.push(9);q.push(5);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;
}int main()
{test_queue();return 0;
}

deque了解

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组

为什么选deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

选deque是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

priority_queue

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成
堆的结构，因此priority_queue就是堆

默认的Compare是less，也就是大堆
想创建的是小堆，可以用greater

priority_queue<int,vector<int>,greater<int>> q

使用sort和priority_queue时参数是不同的

priority_queue模拟实现

#include<iostream>
#include<vector>
#include<queue>
using namespace std;template<class T>
class Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<class T>
class Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};namespace my_pq
{template<class T,class Comtainer = vector<T>,class Compare = Less<T>>class priority_queue{public:priority_queue(){}//根据迭代器区间初始化template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//向下调整size_t n = _con.size();for (size_t i = (n - 2) / 2; i >= 0; i--){adjust_down(i);}}void adjust_up(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[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){Compare com;int child = parent * 2 + 1;size_t n = _con.size();while (child < n){//if (child + 1 < n//	&& _con[child] < _con[child + 1])if (child + 1 < n&& com(_con[child], _con[child + 1])){++child;}//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);//向上调整，传child}void pop(){swap(_con[0],_con[_con.size()-1]);//交换堆顶到末尾再删除_con.pop_back();adjust_down(0);//向下调整，传parent}const T& top(){return _con[0];}bool empty(){return _con.empty();}private:Comtainer _con;};
}
int main()
{//my_pq::priority_queue<int> q;my_pq::priority_queue<int,vector<int>,Greater<int>> q;q.push(2);q.push(1);q.push(5);q.push(3);while (!q.empty()){cout << q.top() << " ";q.pop();}return 0;
}

仿函数

在模拟实现优先级队列的时候，priority_queue是大堆还是小堆取决于比较方法，可以用函数指针，但函数指针可读性不是很好，为了替代函数指针，仿函数就是个好方法