前言

stack和list的使用就不讲了，讲一下模拟实现，然后讲一下deque，最后讲一下优先队列

1. stack的模拟实现

	template<class T,class container>//这个container是vector，或者list或者deque（后面会说），这就叫做适配器，//用适配器来实现stack//就免去了很多我们要实现的东西class stack{public://stack();可以不用写void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.enmpty();}private:container _con;};

template<class T,class container>
这个container是vector，或者list或者deque（后面会说），这就叫做适配器，
用适配器来实现stack
就免去了很多我们要实现的东西
因为vector，list这些适配器都有pop_back，这些函数，所以不管是哪个适配器都是可以实现这个栈的

		stack<int,vector<int>> s;s.push(1);s.push(2);s.push(3);s.push(4);s.push(5);s.push(6);while (!s.empty()){cout << s.top() << endl;s.pop();}cout << endl;

然后这样调用，这个模版参数，模版列表，就相当于函数那样，int传给T,vector传给container，然后就可以正常操作了，因为像函数那样，所以模版参数也可以设置缺省值

template<class T,class container=deque<T>>

这里既可以设置vector为缺省值，也可以设置list，但我们一般设置deque，队列也是这样的

stack<int> s;

2. queue的模拟实现

namespace bit
{template<class T, class container = deque<T>>class queue{public://stack();可以不用写//因为有默认构造void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}T& top(){return _con.front();}const T& top()const{return _con.front();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:container _con;};void test2(){queue<int> s;s.push(1);s.push(2);s.push(3);s.push(4);s.push(5);s.push(6);while (!s.empty()){cout << s.top() << endl;s.pop();}cout << endl;}
}

这个就没什么好说的了，和stack差不多，唯一值得说的就是，那个模版参数的缺省值不能设置vetor，第一是因为vector没有头插这个函数，第二就是vector头插效率太低了

3. deque相关讲解

deque也叫做双端列表

双端列表的底层大致结构就是这样的，有一个指针数组，指针数组也不是从头开始的，而是从中间某个位置开始指向一些小数组，小数组的大小一般是固定的，比如都是10个

如果要尾插入数据，就会在末尾的小数组后面插入数据，小数组满了，就在这个末尾小数组后面在开辟，头插入数据，就在最前面的小数组前面插入数据，满了继续开辟就是了
deque还支持随机访问，也就是[]访问，因为每个小数组长度固定，就可以通过/10和%10来快速确定位置，所以访问也很快，但是访问没有vector快
但是呢，deque的中间插入就很坑了，要大量挪动后面的小数组
所以说deque这个东西呢，头插头删，尾插尾删很方便，其余的都一般，正是因为其余的一般般，所以无法替代vector和list，因为头插头删，尾插尾删很方便，所以适合作为栈和队列的适配器
下面讲一下大致怎么实现的

deque最主要的内容就是迭代器了，上图的starrt和finish就是迭代器，deque就是全程依靠迭代器实现的cur指向那个小数组里的某个数据当前位置，first指向小数组的头，last指向小数组的尾，node是个二级指针，指向指针数组里的指向小数组的值，就这样就可以很快实现deque了
所以说呢，deque就相当于是vector和list的结合体
还有就是，它的头文件就是deque

4. 优先级队列priority_queue

这个的头文件就是queue，这个东西就类似堆，或者说就是堆，底层是一个数组，使用和堆一摸一样的，因为底层是一个数组，所以我们可以用vector作为适配器
讲priority_queue的实现前，我们先讲一下使用

priority_queue首先它没有initializer_list的构造，所以不能这样，但它支持迭代器的赋值

	int arr[] = { 1,2,34,5,7,8,9,07,6,5,5,4,3,3 };priority_queue<int> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

首先要说的就是，对于正常的数组，它的指针就是就是它的迭代器
然后因为是堆嘛，每次出数据，调整数据，那肯定是有序的，看的出来，我们这个实现的是大堆

	int arr[] = { 1,2,34,5,7,8,9,07,6,5,5,4,3,3 };priority_queue<int,vector<int>,greater<int>> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

如果要实现成小堆的话，就要加上greater了，其实如果是排序的话，也是一样的，我们调用的排序，默认是升序的，但是如果加上greater，那么就是降序的了，因为编译器默认的模版参数是less，less是升序的，因为greater在priority_queue中是第三个参数，所以要传greater就要先传vector，vector是第二个模版参数，而且还是默认值
下面我们开始priority_queue的模拟实现
先实现一个大堆，先不管greater怎么搞的
在此之前，先提醒一点模版中的语法错误是不会直接用红线报出来的，比如你用的中文符号就不会直接报错来

	template<class T,class container=vector<T>>class priority_queue{public:priority_queue() = default;//我们先写个迭代器区间构造template<class my_iterator>priority_queue(my_iterator first, my_iterator end){while (first != end){_con.push_back(*first);first++;}//在把这个写成堆int child = (_con[(_con.size() - 1 - 1) / 2]);//从这个位置开始向下调整while (child >= 0){Adjust_down(child);child--;}}void Adjust_down(int parent){int child = 2 * parent + 1;while (child < _con.size()){if ((child + 1) < _con.size() && _con[child + 1] > _con[child]){child++;}if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = 2 * child + 1;}else{break;}}}void Adjust_up(int child){int parent = (child - 1) / 2;while (child > 0)//child等于0，就说明已经比较完了{if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T&x){//先插入vector，然后在向上调整_con.push_back(x);Adjust_up((int)_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();Adjust_down(0);}T& top(){return _con[0];}const T& top()const{return _con[0];}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:container _con;};

		int arr[] = { 1,2,34,5,7,8,9,7,6,5,5,4,3,3 };priority_queue<int> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

我们这个建立的是大堆，如何建立小堆呢，其实只需要将大堆的函数的>改成<,<改成>就可以了
但是这样还要写一个模版吗，其实还有一个更简单的方法，就是仿函数的方法

	template<class T>class myless{bool operator()(T& t1, T& t2){return t1 < t2;}};

如上图，这就是个仿函数，所谓仿函数就是对()的重载，使类产生的对象可以像函数那样去使用

		myless<int> m;cout << m(1, 2) << endl;

以前的重载，比如operator<;就是这样使用的m<T,小于始终只有一个操作数，但是（）的重载，操作数就可以有很多个，而且返回值不唯一，也可以有很多

	template<class T>class myless{public:bool operator()(const T& t1,const T& t2){return t1 < t2;}};template<class T>class mygreater{public:bool operator()(const T& t1, const T& t2){return t1 > t2;}};

所以两个仿函数就这样定义

void Adjust_down(int parent){int child = 2 * parent + 1;while (child < _con.size()){if ((child + 1) < _con.size() && _con[child + 1] > _con[child]){child++;}compare a;if (a(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = 2 * child + 1;}else{break;}}}void Adjust_up(int child){int parent = (child - 1) / 2;while (child > 0)//child等于0，就说明已经比较完了{compare a;if (a(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

对应函数就这样写，这样的话，就实现了大于小于的切换了，只需要传入less和greater就可以了，这里我们防止与库里的less冲突，所以才这样命名

		int arr[] = { 1,2,34,5,7,8,9,7,6,5,5,4,3,3 };priority_queue<int,vector<int>,mygreater<int>> a(arr, arr + sizeof(arr) / sizeof(arr[0]));while (!a.empty()){cout << a.top() << " ";a.pop();}

以后还会经常用到仿函数的

5. 练习题

5.1 最小栈

class MinStack {
public:MinStack() {//不用写}void push(int val) {stack1.push(val);if (stack2.empty() || stack2.top() >= val)//为空，或者val就是最小数据{stack2.push(val);}}void pop() {int tmp = stack1.top();stack1.pop();if (tmp == stack2.top()){stack2.pop();}}int top() {return stack1.top();}int getMin() {return stack2.top();}
private:stack<int> stack1;stack<int> stack2;
};

5.2 栈的压入、弹出序列

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param pushV int整型vector* @param popV int整型vector* @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code here//stack<int> s1;//int i = 0;//int j = 0;//s1.push(pushV[i]);//i++;//while (i < pushV.size())//如果这样设计的话，那么最后一个元素入栈，后就直接跳出来了，还没有判断后面的是否对应//    while (i < pushV.size())//但取了等于就永远死循环了，太麻烦了//    {//        while(!s1.empty()&&popV[j] == s1.top())//因为为空无法访问//        {//            s1.pop();//            j++;//        }//        if(s1.empty()|| popV[j] != s1.top())//        {//            s1.push(pushV[i]);//            i++;//        }//    }//    if (!s1.empty())//    {//        return false;//    }//    else//    {//        return true;//    }//}stack<int> s1;int i = 0;int j = 0;while (i < pushV.size())//交换一下位置呢//先入栈在判断是否对应{if (s1.empty() || popV[j] != s1.top()){s1.push(pushV[i]);i++;}while (!s1.empty() && popV[j] == s1.top())//因为为空无法访问{s1.pop();j++;}}if (!s1.empty()){return false;}else{return true;}}
};

5.3 数组中的第K个最大元素