C++队列-白红宇

C++队列

阅读量：5081 次

发布时间：2019-06-12

本文共 2340 字，大约阅读时间需要 7 分钟。

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，用来在队列头尾进行插入删除元素。

与vector不同的是，deque不支持reserve。如果要提前分配空间，可利用构造函数或deque::resize分配空间并同时进行初始化。

队列

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

构造函数示例：

std::deque
    
      dque{ 1,2,3 };//deque,初始化列表，以下三个queue的核心数据成员类型，    std::queue

> que0;//默认构造 std::queue

> que2(que1);//复制构造 std::queue

> que1(dque);//使用const container_type&构造

接口：

成员函数	说明
`back`	返回尾元素（最后添加的元素）的引用
`empty`	返回`bool`，队列是否为空
`front`	返回首元素的引用
`pop`	无返回值，删除头元素
`push`	无返回值，在队列尾部添加一个元素
`size`	返回`size_t`，队列中元素的个数

优先队列

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

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

push

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

pop

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

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

build

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

int a[] = { 1,5,2,3,6,4 };std::priority_queue

, std::less

>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
    
     , std::less
     
       >pqAA;//char最大的排在队首struct grt//针对BB类设计的仿std::greater类{    bool operator()(const BB& lval, const BB& rval)    {return lval.c > rval.c;}};std::priority_queue
      
       , grt>pqBB;//char最小的排在队首//BB的例子也可以这样写auto cmp = [](const BB& lval, const BB& rval) {return lval.c > rval.c; };std::priority_queue
       
        , decltype(cmp)>pqBB(cmp);

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