目录
stack介绍
栈的结构
栈接口的使用
栈的基本题目
最小栈
栈的弹出压入序列
二叉树的分层遍历
栈的模拟实现
stack.h文件
队列的介绍
队列的结构
队列接口的使用
队列的模拟实现
priority_queue的介绍和使用
接口使用
优先级队列的题目应用
数组中第k大的数字
优先级队列的模拟实现
priority_queue.h文件
deque的介绍
deque的缺陷
stack介绍
我们可以搜一些资料学习栈：栈文档
栈的结构
我们很熟悉了，栈的结构：
栈接口的使用
这些接口比较简单，这里不过多赘述！
栈的基本题目
最小栈
地址：最小栈
思路：
题目的本质是，我们要得到一个栈中的最小元素！
我们可以用两个栈实现一个栈的功能：
定义一个栈_st,里面存储所有插入进来的数据，定义另一个栈_minst,存储小数据，不管在什么时候我们都保证它的栈顶元素是所有数据最小的数。
于是，我们拿栈中的最小元素，只需要返回_minst的栈顶元素即可！
那么关键就在于怎么进行插入和删除的操作而已！
插入时，无论什么数据，_st都要插入，当_minst是空的时候，或者插入的元素小于_minst的栈顶元素时，_minst也插入！
删除时，无论什么数据，_st都要删除，当要删除的元素等于_minst的栈顶元素时，_minst也删除！
代码：
class MinStack {
public:MinStack() {}void push(int val) {//无论如何_st，_st都要push_st.push(val);//当_minst为空，或者栈顶元素小于或等于val，_minst也pushif(_minst.empty()||val<=_minst.top())_minst.push(val);}void pop() {//当_st栈顶的元素和_minst栈顶元素相等，_minst也popif(_st.top()==_minst.top())_minst.pop();//无论如何，_st都要pop_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;//存储所有数据//存储小数据，无论什么时候，它的栈顶一定是所有数据最小的那个stack<int> _minst;
};
栈的弹出压入序列
地址：栈的弹出压入序列
思路：
我们需要模拟入栈出栈即可！
遍历压入序列，入栈，用 i 记录出栈序列的下标，当栈顶元素和出栈序列相等时，出栈，同时 i++，往前走，当栈顶元素和出栈序列不相等时，继续遍历入栈！
有一种情况：比如压入序列：2，1，0,弹出序列：1，2，0。
当入栈到1时，一直出栈到空，此时0还没有入栈，然后判断条件栈顶元素和出栈序列相等，判断不了，因为此时栈是空的，没有栈顶元素，所以我们需要加一个判断条件：栈不为空！
代码：
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> _st;size_t i=0;//遍历popV//遍历插入for(auto& e:pushV){_st.push(e);//当栈顶元素和popV的元素相等，栈popwhile(!_st.empty()&&_st.top()==popV[i]){_st.pop();i++;}}return _st.empty();}二叉树的分层遍历
地址：二叉树的层序遍历
思路：
我们首先让根节点先进入队列，根据对头左右节点有就继续进队列，然后队头出队列，循环往复。
只是我们需要插入进一个二维数组，我们可以将这颗树的每一层有多少个节点记录下来！
代码：
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;vector<vector<int>> vv;int lsize;if(root){q.push(root);lsize=1;}while(!q.empty()){vector<int> v;while(lsize--){if(q.front()->left)q.push(q.front()->left);if(q.front()->right)q.push(q.front()->right);v.push_back(q.front()->val);q.pop();}lsize=q.size();vv.push_back(v);}return vv;}
};栈的模拟实现
我们仔细观察栈的结构（先进后出），仔细想一下，发现我们可以用一个动态数组来实现它（也可以用链表），
所以我们可以用vector来包装它！
这样就简单很多！
stack.h文件
#include<iostream>
#include<vector>
namespace ywc
{template<class T>class stack{public:bool empty(){return _s.empty();}size_t size(){return _s.size();}const T& top(){return _s.back();}void push(const T& x){_s.push_back(x);}void pop(){_s.pop_back();}private:std::vector<T> _s;};
}当然，也能用链表实现！这里不过多赘述！
队列的介绍
文档：队列文档
队列的结构
队列接口的使用
这里也不过多赘述，比较简单！
队列的模拟实现
队列是先进先出，需要头删，用一个动态数组效率太慢，所以我们采用链表！
我们可以用一个list来包装！
代码：
#include<iostream>
#include<list>
namespace ywc
{template<class T>class queue{
public:bool empty(){return _lt.empty();}size_t size(){return _lt.size();}const T& front(){return _lt.front();}const T& back(){return _lt.back();}void push(const T& x){_lt.push_back(x);}void pop(){_lt.pop_front();}
private:std::list<T> _lt;};
}priority_queue的介绍和使用
优先级队列的文档：优先级队列文档
简单介绍一下优先级队列：
不管什么时候，它的第一个元素总是最大的！也能随时插入元素，且只能检索顶部数据，且要删除数据也是删除顶部数据！
所以：
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。
简单赘述：
优先级队列是底层是一个动态数组（堆），在数组尾部插入，然后利用向上调整法调整数据的分布从而符合堆的特性（大小堆），删除数据时，删除第一个数据，然后利用向下调整法调整数据的分布从而符合堆的特性！
接口使用
接口比较简单，这里不过多赘述！
我们来看一下它的大小堆特性：
但当我们的类型是自定义类型的话：
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重 载。
如：
优先级队列的题目应用
数组中第k大的数字
地址：数组中第k个大的数字
思路：
我们可以将数组中的数全部放进一个大堆中，然后将前k-1个数删掉，然后栈顶就是我们的第k个大的数字！
代码：
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//将数组中的数全部放在一个大堆中priority_queue<int> q;for(auto& e:nums)q.push(e);while(--k)//将前k-1个数字pop掉q.pop();return q.top();}
};优先级队列的模拟实现
根据刚才我们所说的它的特点来包装它，并且参照STL库中的方式！
我们的思路：
priority_queue.h文件
#pragma once#include<iostream>
#include<vector>
#include<algorithm>
namespace ywc
{template<class T>struct less{bool operator()(const T& a, const T& b){return a < b;}};template<class T>struct greater{bool operator()(const T& a, const T& b){return a > b;}};template<class T,class Container=std::vector<T>,class Compare=less<T>>class priority_queue{public:void push(const T& x){_c.push_back(x);//向上调整AdjustUp(size() - 1);}void pop(){std::swap(_c[0], _c[size() - 1]);_c.pop_back();//向下调整AdjustDown(0);}bool empty(){return size() == 0;}const T& top(){return _c.front();}size_t size() const{return _c.size();}private://向上调整void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0)//当孩子等于0时跳出{if (Compare()(_c[parent],_c[child])){std::swap(_c[child], _c[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//向下调整void AdjustDown(int parent){int child = parent * 2 + 1;while (child < size()){//假设法，假设左右孩子大小if (child + 1 < size() && Compare()(_c[child ] , _c[child+1])){child++;}if (Compare()(_c[parent] , _c[child])){std::swap(_c[child], _c[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}Container _c;};
}
deque的介绍
先前讲过stack底层是vector,queue底层是list，但其实在STL库中，stack和queue底层默认的容器是deque.
我们现在来介绍一下deque:
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
结构：
注意：deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组。
如图：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问 的假象，落在了deque的迭代器身上。
deque的缺陷
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩 容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实 际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
为什么选择deque作为stack和queue的底层默认容器？
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的 元素增长时，deque不仅效率高，而且内存使用率高。
我们下期见！！！
