C++ 队列

C++队列

默认已熟悉std::vector。vector是一个极其重要的模板，其中的每一个函数都应该了解其作用与用法，这里不再赘述。

双向队列

双向队列（std::deque）类似于vector，允许快速随机访问任何元素并在容器后面高效插入和删除。 但是，和矢量不同的是， deque还支持在容器前面高效插入和删除。使用时需加入头文件<deque>

deque虽名为队列，但是同时支持一些非队列操作。比如，deque::insert和deque::erase可在deque中的任意位置插入和删除元素。其常用的几个操作为deque::push_back、deque::pop_back、deque::push_front和deque::pop_front，用来在队列头尾进行插入删除元素。

与 std::vector 相反， deque 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 vector 的下标访问只进行一次(来自cppreference)。因此，相对于vector，deque没有reserve方法。

队列

队列（std::queue）是一种先进先出的结构。相较与双向队列，它只保留了最必要的部分。默认使用deque作为核心数据成员，可以改为list。

构造函数示例：

    std::deque<int> dque{ 1,2,3 };//deque,初始化列表，以下三个queue的核心数据成员类型，
    std::queue<int, std::deque<int>> que0;//默认构造
    std::queue<int, std::deque<int>> que2(que1);//复制构造
    std::queue<int, std::deque<int>> que1(dque);//使用const container_type&构造

接口：

优先队列

优先队列（std::priority_queue）是一种二叉堆结构，C++默认为最大堆。它不是先进先出，而是优先顺序最大者先出。优先队列默认使用vector作为核心数据成员。优先队列中某一节点的值要比其下所有节点值的优先顺序更高。

下图中的第一个子图是一个优先队列的示例，大值优先。队首为6，不小于任意其它元素，是整个队列的最大值。队列中的任意节点都不小于其直接或间接子节点的值。

上图演示了队尾插入元素的过程，下图演示了删除队首元素的过程。

若在第一步（右上图）中交换首尾元素而不是进行替换，就使最大值排在最后的位置。然后把队列的长度变量减1，不断重复此过程，就可以得到一个升序的序列。此方法被称为堆排序。

若从一个数组中构建一个优先队列，可以使用第一幅图中将元素一个个插入的方法，也可以使用如下的方法。

priority_queue没有back接口，因为此位置的值是不确定的，有一个top接口对应front。

int a[] = { 1,5,2,3,6,4 };
std::priority_queue<int, std::vector<int>, std::less<int>>dat(a, a + 6);

上面示例使用数组a中的元素构建了一个大值优先队列。尖括号中第一个int说明队列元素类型，第二个vector<int>说明队列的数据成员使用的是vector，最后一个less<int>说明队列是最大堆。less是一个类模板，但是重载了小括号，其行为类似于函数。在下面的示例中可以看到其实现细节。

struct AA
{
    int i;
    char c;
    //AA重载了小于，且两个参数都是const的，否则less中不能填入AA类型
    bool operator<(const AA& rval) const
    {return c < rval.c;}
};

struct BB//BB没有对操作符进行重载
{
    int i;
    char c;
};

std::priority_queue<AA, std::vector<AA>, std::less<AA> >pqAA;//char最大的排在队首

struct grt//针对BB类设计的仿std::greater类
{
    bool operator()(const BB& lval, const BB& rval)
    {return lval.c > rval.c;}
};
std::priority_queue<BB, std::vector<BB>, grt>pqBB;//char最小的排在队首

//BB的例子也可以这样写
auto cmp = [](const BB& lval, const BB& rval) {return lval.c > rval.c; };
std::priority_queue<BB, std::vector<BB>, decltype(cmp)>pqBB(cmp);

优先规则的确定在于，在尖括号中输入一个类名，构造函数中给出该类的一个对象，使用该对象应该能够对队列中的元素进行比较。若构造函数中将其省略，默认造成的对象能否依旧完成此任务。对于grt，其默认生成的对象也能进行BB之间的比较，而对于lambda，它接收两个const BB&返回bool。但如果定义一个此类型的对象，我们知道它可以对BB进行比较，但是却不知道比较规则，因此队列构造函数中的的对应参数就不能省略。