STL中的stack和queue介绍及模拟实现（C++）
stack
stack指的是栈，它的机制是后进先出或先进后出
stack的接口
| push() | 栈顶入数据 |
| pop() | 栈顶出数据 |
| stack() | 建立一个空栈 |
| size() | 获取有效数据个数 |
| empty() | 判断栈是否为空 |
| top() | 获取栈顶数据 |
stack的模拟实现
在模拟实现我们先引入一个问题，stack可以用哪些数据结构（string、vector、list、queue、deque(deque是双端队列，是vector和list的结合，顾名思义，双端均可实现效率较高的插入删除，还可以实现下标访问)）高效实现？queue可以用哪些数据结构高效实现？
既然stack和queue的底层是用这些数据结构来实现，我们引入容器适配器概念，容器适配器是将一个类的接口转换成客户希望的另外一个接口，就如stack和queue底层是其他数据结构，但我们调用stack和queue时把它们作为一种数据结构，实现了转换。那么如何实现呢？在设计stack和queue的模板时增添一个模板参数，让它作为stack和queue的底层数据结构，再在底层上实现stack和queue的功能。C++还实现了模板参数缺省的功能，如下
那么我们为什么要让deque作为stack和queue默认的底层呢？
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性 结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据 结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如 list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作
在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高
结合了deque的优点，而完美的避开了其缺陷
deque总结
deque结合了vector和list的优点，但相比vector和list优点都不够极致
| vector | list | deque | |
| 优点 | 1.尾插尾删效率高 2.随机访问速度快 3.cpu高速缓存命中率高 | 1.任意位置插入删除效率高 2.仅插入删除当前迭代器失效 3.扩容不需要拷贝旧数据，不存在容量概念 | 1.头部尾部插入删除效率都高 2.cpu高速缓存命中率较高 3.支持随机访问，但效率不如vector 4.扩容不需要拷贝旧数据 |
| 缺点 | 1.头部以及中间插入删除效率低 2.扩容可能要复制旧数据 | 1.cpu高速缓存命中率低 2.随机访问效率低 | 1.中间位置插入删除效率低 2.内部结构较复杂，迭代器开销大 |
queue
queue是队列，是一种容器适配器，机制是先进先出
queue的接口
| queue() | 构造空队列 |
| empty() | 判断是否为空 |
| size() | 获取有效数据个数 |
| front() | 获取队头元素 |
| back() | 获取队尾元素 |
| push() | 队尾入数据 |
| pop() | 队头出数据 |
queue的模拟实现
priority_queue
优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的，由此可以想到它的底层是堆，而堆的底层可以是vector和deque，默认数据结构为vector，因为其所需操作vector均可胜任，而vector结构简单，开销小。
因此priority_queue就是堆，所有考虑用到堆的地方，都可以考虑priority_queue，但要注意默认情况下priority_queue是大堆
priority_queue的接口
| priority_queue()/priority_queue(first,last) | 构造一个优先级队列（空/复制另一个容器的数据） |
| empty() | 判断是否为空 |
| top() | 返回堆顶元素，即优先级队列的最大（最小）元素 |
| push() | 优先级队列插入元素 |
| pop() | 删除堆顶元素，即优先级队列的最大（最小）元素 |
priority_queue的模拟实现
在模拟实现之前引入仿函数概念，其实就是用类中的成员函数operator()，其形式与函数十分相像，但语义不同（匿名对象（也可以是有名对象）调用operator()函数）
sort(v.begin(),v.end(),std::greater<int>());//greater<int>()即为仿函数其设计目的是弥补函数指针的缺陷
上图模板参数中的第三个是用来控制priority_queue是大堆还是小堆，如果传函数指针，这样Compare仅仅只是函数指针类型，无法实例化发挥其作用。仿函数可以直接用来比较，也可以根据需求来控制比较逻辑（如一个类内部未实现比较，可以通过仿函数内部代码来实现比较逻辑），还有更多场景我们以后还会遇到