<span data-docs-delta="[[20, " 一、什么是="" deque",="" "31:2|inline-dir:"ltr""],="" [20,="" "\n",="" "24:"ey4i"|32:2|direction:"ltr""],="" "deque="" 也是顺序容器的一种，也是一个可变长数组。要使用="" deque，需要包含头文件="" deque。所有适用于="" vector="" 的操作都适用于="" deque，deque="" 在头尾增删元素性能较好。",="" "27:"12"|31:2|inline-dir:"ltr""],="" "24:"43zc"|direction:"ltr""],="" "24:"fvgx""],="" 的特点",="" "0:"initial"|31:2|inline-dir:"ltr""],="" "：",="" "0:"var(--md-box-samantha-normal-text-color)"|31:2"],="" "0:"var(--md-box-samantha-normal-text-color)"|24:"3wug"|direction:"ltr"|heading:"3"|list-id:"adlm"|ordered:"decimal""],="" 和="" 有很多类似的地方。在="" deque="" 中，随机存取任何元素都能在常数时间内完成（但慢于="" vector）。",="" "0:"initial"|inline-dir:"ltr""],="" "0:"initial"|24:"etdb"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" "它相比于="" 的优点是，vector="" 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而="" 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。",="" "0:"initial"|24:"byfe"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" 有两种="" 没有的成员函数",="" "0:"var(--md-box-samantha-normal-text-color)"|24:"ma3u"|direction:"ltr"|heading:"3"|list-id:"adlm"|ordered:"decimal""],="" "void="" push_front="" (const="" t="" &="" val);="" 将="" val="" 插入容器的头部",="" "0:"initial"|24:"p8h2"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" pop_front="" ();="" 删除容器头部的元素",="" "0:"initial"|24:"ufrp"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" 使用注意",="" "0:"var(--md-box-samantha-normal-text-color)"|24:"3q45"|direction:"ltr"|heading:"3"|list-id:"adlm"|ordered:"decimal""],="" 支持随机存取",="" "0:"initial"|24:"ovnh"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" 支持在头部和尾部存储数据",="" "0:"initial"|24:"qmgr"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" 不支持="" capacity="" reserve="" 操作",="" "0:"initial"|24:"7ucm"|33:1|direction:"ltr"|list-id:"adlm"|ordered:"decimal""],="" "24:"poqt"|direction:"ltr""],="" "二、deque="" 的应用",="" "24:"epse"|32:2|direction:"ltr""],="" "例子：在头尾添加、删除函数",="" "24:"cfrg"|direction:"ltr""],="" "(1)="" 头部添加元素：push_front="" t&="" x);",="" "24:"vjqc"|direction:"ltr""],="" "(2)="" 头部删除元素：pop_front="" ();",="" "27:"12"|31:2|inline-dir:"ltr""]]"="" data-copy-origin="https://shimo.im">

双向队列（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的常见函数

<span data-docs-delta="[[20, " 优先队列（priority_queue）",="" "inline-dir:\"ltr\""],="" [20,="" "\n",="" "24:\"sssr\"|32:1|direction:\"ltr\""],="" "priority_queue",="" "0:\"initial\"|27:\"12\"|code:true"],="" "是="" “优先队列”。它和普通队列的区别在于，优先队列的队头元素总是最大的="" ——="" 即执行",="" "27:\"12\"|31:2"],="" "pop",="" "操作时，",="" "删除的总是最大的元素",="" "0:\"rgb(255%2c%200%2c%200)\"|27:\"12\"|31:2"],="" "；执行",="" "top",="" "操作时，返回的是最大元素的引用。",="" "24:\"ehux\"|direction:\"ltr\""],="" "24:\"7cbd\""],="" "可以用",="" "0:\"var(--md-box-samantha-normal-text-color)\"|27:\"12\"|31:2"],="" "vector",="" "和",="" "deque",="" "实现，默认情况下用",="" "实现。",="" "0:\"var(--md-box-samantha-normal-text-color)\"|24:\"6gyj\"|27:\"12\"|bullet-id:\"8hp6\"|bullet:\"circle\"|direction:\"ltr\""],="" "默认的元素比较器是",="" "less="" <y” 必为",="" "0:\"var(--md-box-samantha-normal-text-color)\"|27:\"12\"|31:2"],="" [20,="" "false",="" "0:\"initial\"|27:\"12\"|code:true"],="" "。",="" "\n",="" "0:\"var(--md-box-samantha-normal-text-color)\"|24:\"p3gz\"|27:\"12\"|bullet-id:\"8hp6\"|bullet:\"circle\"|direction:\"ltr\""],="" "priority_queue",="" "的第三个类型参数可以用来指定排序规则。",="" "0:\"var(--md-box-samantha-normal-text-color)\"|24:\"3cjk\"|27:\"12\"|bullet-id:\"8hp6\"|bullet:\"circle\"|direction:\"ltr\""],="" "优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序。",="" "0:\"var(--md-box-samantha-normal-text-color)\"|27:\"12\"|31:2|inline-dir:\"ltr\""],="" "0:\"var(--md-box-samantha-normal-text-color)\"|24:\"pckw\"|27:\"12\"|bullet-id:\"8hp6\"|bullet:\"circle\"|direction:\"ltr\""],="" "内部",="" "并非完全有序",="" "0:\"rgb(255%2c%200%2c%200)\"|27:\"12\"|31:2"],="" "，但却能确保最大元素总在队头。",="" "0:\"var(--md-box-samantha-normal-text-color)\"|24:\"e3zd\"|27:\"12\"|bullet-id:\"8hp6\"|bullet:\"circle\"|direction:\"ltr\""],="" "24:\"ukhe\"|direction:\"ltr\""],="" "24:\"2bmm\"|direction:\"ltr\""],="" "定义：",="" "27:\"12\"|31:2|inline-dir:\"ltr\""],="" "priority_queue

优先队列（priority_queue）

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

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

定义：priority_queue

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

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

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