---

1. stack

1.1 简单了解stack

1. stack是一种容器适配器，是通过对特殊类或者容器的封装，获得想要的容器。stack的底层是类或者容器。
2. stack支持后进先出，只能在一端进行操作。
3. stack的底层容器应该支持stack的基本操作，例如push_back()尾插，pop_back()尾删，empty()判断栈空等操作。
4. stack默认使用deque作为底层容器（后面讲），而vector、list也满足条件。

1.2 stack的常见接口

void test()
{//构造stack<int> st;//push尾插st.push(1);st.push(2);st.push(3);st.push(4);//empty判断为空while (!st.empty()){//top输出栈顶元素cout << st.top() << " ";//pop尾删st.pop();}cout << endl;
}
//结果
//4 3 2 1

1.3 练习

1. 最小栈（LeetCode155）

//思路：利用两个栈，_st将元素正常入栈，_minSt比较入栈元素和栈顶元素，
//小于或者等于栈顶元素就入栈;出栈时，如果_st的栈顶元素和_minSt的栈顶元素相同就一同出栈
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()){_st.pop();_minSt.pop();}else{_st.pop();}}int top() {return _st.top();}int getMin() {return _minSt.top();}
private:stack<int> _st;//用来存储正常元素stack<int> _minSt; //用来存储最小元素
};

2. 栈的压入和弹出序列（牛客）

 //根据入栈序列判断出栈序列是否正确bool IsPopOrder(vector<int>& pushV, vector<int>& popV){// write code herestack<int> st;//用来入栈和出栈int ipushV = 0;//用来记录入栈序列的下标int ipopV = 0;//用来记录出栈序列的下标//当入栈顶序列的元素都入栈顶后，停止循环while(ipushV<pushV.size()){//直接入栈st.push(pushV[ipushV++]);//判断栈顶元素是否和出栈序列相同//不同就继续入栈，相同就出栈，依次与出栈序列比较if(st.top()!=popV[ipopV]){continue;}else {while(!st.empty()&&st.top()==popV[ipopV]){st.pop();++ipopV;}}}//如果为空，说明出栈序列为真return st.empty();}

3. 逆波兰表达式求值（LeetCode150）

class Solution {
public://（1）逆波兰表达式是后缀表达式。//（2）用后缀表达式计算出表达式的值，需要用到栈。//（3）首先将操作数入栈，然后遇到操作符就取出栈顶两个元素进行运算，同时将计算结果入栈。int evalRPN(vector<string>& tokens) {stack<int> st;for(size_t i = 0;i<tokens.size();i++){if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){//注意：先取出的是右操作数int right = st.top();st.pop();int left = st.top();st.pop();//tokens每个元素都是string类型switch(tokens[i][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(tokens[i]));}}return st.top();}
};

1.4 模拟实现stack

namespace zn
{//stack默认适配的容器是deque，deque后面会讲到template<class T,class Container = deque<T>>class stack{Container _con;public://不用写构造，_con会自动调用其构造void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}bool empty(){return _con.empty();}T& top(){return _con.back();}size_t size(){return _con.size();}};void test_stack(){stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << st.size() << endl;while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;//底层容器也可以用vector和list//stack<int, vector<int>>  st1;stack<int, list<int>> st2;st2.push(1);st2.push(2);st2.push(3);st2.push(4);cout << st2.size() << endl;while (!st2.empty()){cout << st2.top() << " ";st2.pop();}}
}

---

2. queue

2.1 简单了解queue

1. queue也是一种容器适配器。底层是特殊类或者其他容器。
2. queue支持先进先出，只能在一端插入，在另一端删除。
3. queue的底层容器应该支持queue的基本操作，例如push_back尾插，pop_front头删，front输出队头元素，back输出队尾元素等操作。
4. 如果没有为queue指定容器，则默认使用deque。

2.2 queue的常见接口

void test1()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout <<  endl;
}

2.3 练习

1. 二叉树的层序遍历（LeetCode102）

class Solution {
public://思路：从上到下，将一层节点放到一个队列中，用vector<int>记录一层节点的值，将这层节点出队时同时将下一层节点入队（其中为了区分不同层次，利用levelsize记录每层节点的个数），再将vector<int>放到vector<vector<int>>中vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;int levelsize = 0;//记录当前这层的节点个数queue<TreeNode*> q;if(root!=nullptr){q.push(root);levelsize = 1;}while(!q.empty()){vector<int> v;for(size_t i = 0;i<levelsize;i++){TreeNode* tmp = q.front();q.pop();v.push_back(tmp->val);if(tmp->left){q.push(tmp->left);}if(tmp->right){q.push(tmp->right);}}vv.push_back(v);levelsize = q.size();}return vv;}
};

2. 二叉树的层序遍历Ⅱ（LeetCode107）

class Solution {
public://只需在上一题的基础上，加上逆置即可。vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> q;vector<vector<int>> vv;int levelSize;if(root){q.push(root);levelSize = 1;}while(!q.empty()){vector<int> v;for(int i = 0;i<levelSize;i++){TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}levelSize = q.size();vv.push_back(v);}reverse(vv.begin(),vv.end());return vv;}
};

2.4 模拟实现queue

namespace zn
{template<class T,class Container = deque<T>>class queue{Container _con;public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}bool empty(){return _con.empty();}size_t size(){return _con.size();}T& front(){return _con.front();}T& back(){return _con.back();}};void test_queue(){queue<int> qt;qt.push(1);qt.push(2);qt.push(3);qt.push(4);cout << qt.front() << " " << qt.back() << endl;while (!qt.empty()){cout << qt.front() << " ";qt.pop();}cout << endl;//queue的底层容器可以是list，但不适合用vector适配，//因为vector没有提供头删的接口。如果要强制适配，可以用vector.erase(begin())queue<int, list<int>> qt1;qt1.push(1);qt1.push(2);qt1.push(3);qt1.push(4);cout << qt1.front() << " " << qt1.back() << endl;while (!qt1.empty()){cout << qt1.front() << " ";qt1.pop();}cout << endl;}
}

---

3. deque（了解）

deque为什么可以作为stack和queue的底层容器？它到底是什么？它有什么优点和缺点？不急，先了解下deque。

1. deque是双端队列，是可以两端进行插入和删除的容器，具有一段“连续”的内存空间。

2. 因此deque的头插头删和尾插尾删效率非常高，时间复杂度是O(1)，效率比vector高；因为是“连续”的空间，空间利用率比list高。

3. 此处的“连续”并不是指物理上的连续，deque的内存空间是由一段一段的连续空间组成的，类似于二维数组，只不过这个二位数组可以扩容。
   

4. 既然deque这么厉害，为什么只在stack和queue的底层才认识到它？deque看来是弥补了vector和list的缺点。但是没有取得其精华。相比于vector，deque极大缓解了扩容问题、头插头删问题，但下标访问不够极致，得计算在哪一段空间，在那段空间的第几个；相比于list，deque能够支持下标访问，因为空间是一段一段的，CPU高速缓存效率不错，头插头删不错，但中间插入和删除效率低。

5. 综上，什么情况下使用deque最好？需要高频的头插头删和尾插尾删，不适合中间插入和删除以及高频的随机访问。用来适配stack和queue刚刚好（取其精华，去其糟粕）。

---

4. priority_queue

4.1 优先级队列的介绍

1. priority_queue是容器适配器，底层是二叉树的堆，默认是大堆。
2. priority_queue可以支持随机访问，并支持堆的基本操作，例如push_back尾插入，front输出堆顶元素，empty判断堆空，size输出元素数量。
3. priority_queue的底层容器默认是vector，也可以用deque作为底层容器。

4.2 priority_queue的常见接口

void test_priority_queue()
{priority_queue<int> pq;//尾插pq.push(1);pq.push(3);pq.push(4);pq.push(2);//判断是否为空while (!pq.empty()){//输出堆顶元素cout << pq.top() << " ";//尾删（实际上是删除堆顶元素）pq.pop();}cout << endl;
}

4.3 练习

数组中第K个最大元素（LeetCode215）

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//法1：建立大堆，pop（k-1）次，此时堆顶元素就是第k个最大元素// priority_queue<int> pq(nums.begin(),nums.end());// while(--k)// {//     pq.pop();// }// return pq.top();//法2：建立有k个元素的小堆，如果比堆顶元素大就入堆，最终堆顶元素就是第k个最大元素priority_queue<int,vector<int>,greater<int>> pq;size_t i = 0;for(i = 0;i<k;i++){pq.push(nums[i]);}for(;i<nums.size();i++){if(nums[i]>pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
};

4.4 模拟实现priority_queue

namespace zn
{//仿函数本质上是一个类对象，可以像函数一样使用，所以叫仿函数//模拟实现仿函数template<class T>class less{public:bool operator()(const T& left, const T& right){return left < right;}};template<class T>class greater{public:bool operator()(const T& left, const T& right){return left > right;}};//有仿函数，只需要传递不同的仿造函数，不用修改代码，可以实现大堆和小堆template<class T,class Container = vector<T>,class Compare = less<T>>class priority_queue{Container _con;void AdjustDown(int parent){Compare com;int child = 2 * parent + 1;while (child < size()){if (child + 1 < size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void swap(T& left, T& right){T tmp = left;left = right;right = tmp;}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:priority_queue(){}template<class InputIterator>priority_queue(InputIterator begin,InputIterator end){while (begin != end){_con.push_back(*begin);++begin;}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& val){_con.push_back(val);AdjustUp(size()-1);}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();AdjustDown(0);}int size(){return _con.size();}bool empty(){return _con.empty();}T& top(){return _con.front();}};void test(){//建立大堆priority_queue<int> pq;pq.push(1);pq.push(5);pq.push(2);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;//建立小堆priority_queue<int,vector<int>,greater<int>> p;p.push(1);p.push(5);p.push(2);p.push(4);p.push(3);while (!p.empty()){cout << p.top() << " ";p.pop();}cout << endl;}
}