队列-双端队列 可视化交互式动画版

双端队列（Deque）或双端队列（Double Ended Queue）是 队列数据结构 的通用版本 ，允许在两端插入和删除。

双端队列上的操作： 下表显示了在双端队列上执行的一些基本操作及其时间复杂度。

手术	描述	时间复杂度
推前（）	在开头插入元素。	复杂度(1)
推回（）	在末尾添加元素。	复杂度(1)
pop_front()	从双端队列中删除第一个元素。	复杂度(1)
pop_back()	从双端队列中删除最后一个元素。	复杂度(1)
正面（）	从双端队列中获取前面的元素。	复杂度(1)
后退（）	获取双端队列中的最后一个元素。	复杂度(1)
空的（）	检查双端队列是否为空。	复杂度(1)
尺寸（）	确定双端队列中的元素数量。	复杂度(1)

对双端队列执行的其他操作解释如下：
clear() ：从双端队列中删除所有元素。 它使双端队列的大小为 0。erase
() ：从双端队列中删除一个或多个元素。 它需要一个迭代器来指定要删除的第一个元素的位置，以及一个可选的第二个迭代器来指定要删除的最后一个元素的位置。
swap() ：将一个双端队列的内容与另一个双端队列交换。
emplace_front() ：在双端队列的前面插入一个新元素。 它与插入操作类似，但它避免了被插入元素的复制构造函数。
emplace_back() ：在双端队列的末尾插入一个新元素。 它与插入操作类似，但它避免了被插入元素的复制构造函数。
resize() ：将双端队列中的元素数量更改为特定数量。 如果新大小大于当前大小，则将新元素追加到双端队列中。 如果新大小小于当前大小，则会从双端队列中删除元素。
allocate() ：为双端队列中的元素分配新值。 它用新元素替换双端队列的当前内容。
reverse() ：反转双端队列中元素的顺序。
sort() ：按升序对双端队列中的元素进行排序。 它使用小于运算符来比较元素。

Deque的应用： 由于Deque同时支持堆栈和队列操作，因此它可以用作两者。 Deque 数据结构支持 O(1) 时间内的顺时针和逆时针旋转，这在某些应用程序中非常有用。 此外，使用 Deque 可以有效解决需要在两端删除和/或添加元素的问题。 例如，请参阅 大小为 k 的所有子数组的最大值问题。 , 0-1 BFS, 并 找到第一个访问所有汽油泵的循环路径 。 请参阅 wiki 页面 ，了解 A-Steal 作业调度算法的另一个示例，其中使用 Deque 作为两端都需要删除操作。 

Deque 的一些实际应用 ：

• 可用作堆栈和队列，因为它支持这两种操作。
• 存储网络浏览器的历史记录。
• 存储软件应用程序的撤消操作列表。
• 作业调度算法

单调双端队列： 

• 双端队列，按严格升序或严格降序存储元素 
• 为了保持单调性，我们需要删除元素
  • 例如 – 考虑单调（递减）双端队列 dq = {5, 4, 2, 1} 
  • 将 3 插入 dq
    • 所以我们需要删除元素直到 dq.back() < 3 将 3 插入 dq （ 2,1 是删除的元素）
    • 结果 dq = {5, 4, 3}
• 单调双端队列的应用：
  • 它可用于 通过使用单调递减双端队列来获取子数组中的 下一个最大值  （ sliding-window-maximum-of-all-subarrays-of-size-k ）
  • 像这样，它可以用于获取 子数组中的 先前最大值
  • 常用 于  滑动窗口问题（难）

其他应用：

双端队列还有其他一些应用程序，其中包括：

• 回文检查： 双端队列可用于检查单词或短语是否为回文。 通过将单词或短语的每个字符插入双端队列，可以通过比较第一个和最后一个字符、第二个和倒数第二个字符等来检查单词或短语是否是回文。
• 图遍历： 双端队列可用于在图上实现广度优先搜索（BFS）。 BFS 使用队列来跟踪接下来要访问的顶点，在这种情况下，双端队列可以用作队列的替代方案。
• 任务调度程序： 双端队列可用于实现跟踪要执行的任务的任务调度程序。 任务可以添加到双端队列的后面，调度程序可以从双端队列的前面删除任务并执行它们。
• 多级撤消/重做功能： 双端队列可用于在应用程序中实现撤消和重做功能。 每次用户执行操作时，应用程序的当前状态都会被推送到双端队列中。 当用户撤消操作时，双端队列的前面将被弹出，并恢复之前的状态。 当用户重做操作时，下一个状态将从双端队列中弹出。
• 在计算机科学中，双端队列可用于许多算法，如 LRU 缓存 、 循环调度 、 表达式求值 。

语言支持： C++ STL 提供 Deque 的实现为 std::deque ，Java 提供 Deque 接口 。 请参阅 此 了解更多详细信息。 Java 中的双端 队列 Python 中的双端队列
实现：双端队列可以使用 双向链表 或循环数组 来实现。 在这两种实现中，我们都可以在 O(1) 时间内实现所有操作。 我们很快将讨论 Deque 数据结构的 C/C++ 实现。 使用循环数组实现Deque 如果您发现上述代码/算法不正确，请写评论，或者寻找其他方法来解决同样的问题。