Deque |集合1（介绍和应用）

双端队列 是 队列数据结构 允许在两端插入和删除。

Deque上的操作： 主要对队列执行以下四个基本操作：

insertFront（） ：在Deque的前面添加一项。 insertLast（） ：在Deque的后面添加一项。 deleteFront（） ：从Deque前面删除一项。 deleteLast（） ：从Deque后面删除一项。

除上述操作外，还支持以下操作 getFront（） ：从队列中获取前面的项目。 getRear（） ：从队列中获取最后一项。 isEmpty（） ：检查Deque是否为空。 isFull（） ：检查Deque是否已满。

Deque的应用： 由于Deque同时支持堆栈和队列操作，因此它可以同时用作堆栈和队列操作。Deque数据结构支持O（1）时间内的顺时针和逆时针旋转，这在某些应用中很有用。 此外，使用Deque可以有效地解决需要删除和/或添加两端元素的问题。例如，请参见 大小为k的所有子阵列的最大值问题。 , 0-1 BFS 和 找到参观所有汽油泵的第一个循环游览 .

看见 维基页面 例如，A-Steal作业调度算法的另一个示例，其中Deque用作删除操作，需要在两端执行。

语言支持： C++ STL提供了Deque的实现 德克 Java提供了 Deque接口 看见 这 更多细节。 爪哇岛 Python中的Deque

实施： Deque可以使用 双链表 或圆形阵列。在这两种实现中，我们都可以在O（1）时间内实现所有操作。我们将很快讨论Deque数据结构的C/C++实现。

用圆形阵列实现Deque 如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。