双向队列（deque）

一、什么是 deque
</h2>

deque 也是顺序容器的一种，也是一个可变长数组。要使用 deque，需要包含头文件 deque。所有适用于 vector 的操作都适用于 deque，deque 在头尾增删元素性能较好。

 

1. deque 的特点：

1. deque 和 vector 有很多类似的地方。在 deque 中，随机存取任何元素都能在常数时间内完成（但慢于 vector）。
2. 它相比于 vector 的优点是，vector 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而 deque 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。

2. deque 有两种 vector 没有的成员函数：

1. void push_front (const T & val); // 将 val 插入容器的头部
2. void pop_front (); // 删除容器头部的元素

3. deque 使用注意：

1. deque 支持随机存取
2. deque 支持在头部和尾部存储数据
3. deque 不支持 capacity 和 reserve 操作

 

二、deque 的应用

例子：在头尾添加、删除函数

(1) 头部添加元素：push_front (const T& x);

(2) 头部删除元素：pop_front ();

队列（queue）

一、什么是队列

queue：就是 “队列”。队列是先进先出的（First in first out），队头的访问和删除操作只能在队头进行，添加操作只能在队尾进行。不能访问队列中间的元素。

• queue 可以用 list 和 deque 实现，默认情况下用 deque 实现。
• 特点：先进先出（FIFO），队尾进，队头出。

二、queue的常见函数

优先队列（priority_queue）

priority_queue是 “优先队列”。它和普通队列的区别在于，优先队列的队头元素总是最大的 —— 即执行pop操作时，删除的总是最大的元素；执行top操作时，返回的是最大元素的引用。

 

• priority_queue可以用vector和deque实现，默认情况下用vector实现。
• priority_queue默认的元素比较器是less <T>。也就是说，在默认情况下，要放入priority_queue的元素必须是能用 “<” 运算符进行比较的，而且priority_queue保证以下条件总是成立：对于队头的元素x和任意非队头的元素y，表达式 “x<y” 必为false。
• priority_queue的第三个类型参数可以用来指定排序规则。
• 优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序。
• priority_queue内部并非完全有序，但却能确保最大元素总在队头。

 

 

定义：priority_queue<Type, Container, Functional>

 

• Type就是数据类型；
• Container就是容器类型（Container必须是用数组实现的容器，比如vector, deque等等，但不能用list。STL 里面默认用的是vector）；
• Functional就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

 

priority_queue特别适用于 “不停地在一堆元素中取走最大的元素” 这种情况。priority_queue插入和删除元素的复杂度都是。虽然用set/multiset也能完成此项工作，但是priority_queue比它们略快一些。

</span> </div> </h2> </span>