欢迎来到繁星的CSDN，本期内容主要包括stack（栈），queue（队列），priority_queue（堆）

        

    实际上，C++中的stack、queue还有priority_queue与C语言中的内容无异，所以本篇文章主要想去阐述的，是有关stack、queue还有priority_queue的一些接口与实现原理。 

一、deque

    在说明栈、队列以及优先队列是如何实现之前，我们必须阐述deque的相关知识。

    deque是什么？为什么要有deque？以及deque在模拟实现中扮演着什么样的角色？

 

   当我们翻到stl库里的stack和queue的头文件时（只需要在VS2022所在盘搜索stl_queue.h和stl_stack.h即能得到其头文件，这边推荐使用everything软件辅助快速寻找）我们可以看到Sequence的缺省值是deque<_Tp>，Sequence在后续的代码中不难发现是起容器的作用，而_Tp则扮演了stack内存储值的类型。

      deque是什么以及为什么用deque

        

   deque实际上是vector与list的结合体，由多个vector组成，并以list的形式串连起来。

   这么做的好处是什么？

   让我们回想stack和queue的特点，一个是先进先出，一个是后进先出。如果都用vector来储存的话，那么stack需要的是pop_back()，queue需要的是pop_front()。但是用vector来pop_back简单，pop_front就难上加难了，用list的话首尾删除插入倒是方便，但是在存储空间上由于存储的地址不连续性，以及list每个结点所需要存储的信息更多，使得整体耗费的存储空间更大，且首插尾插效率很低。

   于是deque，一个结合了vector与list的东西诞生了。

   很可惜的是，事实上deque结合了vector和list的优点，更结合了vector与list的缺点。进行尾删操作尚且简单，如果进行头删则需要将其他位置所有的数据向前搬一格。如果进行插入操作，则每次插入都有可能多一个同样长度的vector，一插一删之间，deque很可能造成大量的空间浪费，亦或是牺牲了“搬迁”的效率。

    或许在平均效率上deque比单纯用vector或者list更高吧，但stl创建者选用deque的原因我们不得而知。

二、stack和queue的接口

        stack和queue的接口是十分类似的。

push(x);
pop();
empty();
size();
top();//stack
front();//queue
back();//queue

        与string的区别是，string是push_back，但stack和queue是push。string是pop_back，但stack和queue是pop。queue的front和back分别代表第一个元素以及最新被push的元素。stack的top表示栈顶，没有栈底接口。

     为什么要坚持用接口？

       这一点实际上在封装的那一部分已经被提到过了。我们用接口的目的一方面是为了更简单地使用这些复杂的数据结构，一方面是为了数据的安全性，我们只能使用接口对这些结构进行改造，而不能直接从底层的vector或者deque改数据，这种操作对于结构而言是“不合法”的（对于程序而言并没有什么问题）。

三、priority_queue

       优先队列(priority_queue)实际上是堆，其优先性区分了大根堆与小根堆，但值得注意的是，如果需要使用priority_queue，我们需要包的头文件是<queue>。

       template<class T,class Container = std::vector<T>,class Compare = std::less<typename Container::value_type>> class priority_queue; 

        默认的优先队列是大根堆，在日常使用中我们仅仅需要输入堆所存储的数据类型即可。如果需要小根堆，那么就需要输入数据类型，存储容器（一般为vector），以及std::greater<>（递增）。或者自己书写仿函数。

        优先队列的常用接口如下：

push(x);
pop();
top();
empty();
size();

        其中push放入后，优先队列会自动进行排序，top即堆的根，pop即弹出堆的根，size和empty就不过多赘述了。

        下面是大致的模拟实现。

        

#pragma once
#include<deque>
template<class T,class Con = std::deque<T>>
class stack
{
public:stack();void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_back();}T& top() {return _c.back();}const T& top()const {return _c.back();}size_t size()const {return _c.back();}bool empty()const {return _c.empty();}
private:Con _c;
};

#pragma once
#include<deque>
template<class T, class Con = std::deque<T>>class queue
{
public:queue();void push(const T& x) {_c.push_back(x);}void pop() {_c.pop_front();}T& back() {return _c.back();}const T& back()const {return _c.back();}T& front() {return _c.front();}const T& front()const {return _c.front();}size_t size()const {return _c.size();}bool empty()const {return _c.empty();}
private:Con _c;
};

#pragma once
namespace bit
{
#include<vector>
#include<functional>template <class T, class Container = std::vector<T>, class Compare = std::less<T> >class priority_queue{public:priority_queue();template <class InputIterator>priority_queue(InputIterator first, InputIterator last) {std::make_heap(first,last,comp);}bool empty() const {return c.empty();}size_t size() const {return c.size();}T& top() const {return c.front();}void push(const T& x) {x.push_back(x);std::push_heap(c.begin(), c.end(), comp);}void pop() {std::pop_heap(c.begin(), c.end(), comp);c.pop_back();}private:Container c;Compare comp;};
};