原文地址：http://tech.chinaunix.net/a2010/0812/1089/000001089436.shtml
Queue除了前面介绍的实现外，还有一种双向的Queue实现Deque。这种队列允许在队列头和尾部进行入队出队操作，因此在功能上比Queue显然要更复杂。下图描述的是Deque的完整体系图。需要说明的是LinkedList也已经加入了Deque的一部分(LinkedList是从jdk1.2 开始就存在数据结构)。
Deque在Queue的基础上增加了更多的操作方法。
从上图可以看到，Deque不仅具有FIFO的Queue实现，也有FILO的实现，也就是不仅可以实现队列，也可以实现一个堆栈。
同时在Deque的体系结构图中可以看到，实现一个Deque可以使用数组(ArrayDeque)，同时也可以使用链表(LinkedList)，还可以同实现一个支持阻塞的线程安全版本队列LinkedBlockingDeque。
对于数组实现的Deque来说，数据结构上比较简单，只需要一个存储数据的数组以及头尾两个索引即可。由于数组是固定长度的，所以很容易就得到数组的头和尾，那么对于数组的操作只需要移动头和尾的索引即可。
特别说明的是ArrayDeque并不是一个固定大小的队列，每次队列满了以后就将队列容量扩大一倍(doubleCapacity())，因此加入一个元素总是能成功，而且也不会抛出一个异常。也就是说ArrayDeque是一个没有容量限制的队列。
同样继续性能的考虑，使用System.arraycopy复制一个数组比循环设置要高效得多。
对于LinkedList本身而言，数据结构就更简单了，除了一个size用来记录大小外，只有head一个元素Entry。对比Map和Queue的其它数据结构可以看到这里的Entry有两个引用，是双向的队列。
在示意图中，LinkedList总是有一个“傀儡”节点，用来描述队列“头部”，但是并不表示头部元素，它是一个执行null的空节点。
队列一开始只有head一个空元素，然后从尾部加入E1(add/addLast)，head和E1之间建立双向链接。然后继续从尾部加入E2，E2就在head和E1之间建立双向链接。最后从队列的头部加入E3(push/addFirst)，于是E3就在E1和head之间链接双向链接。
双向链表的数据结构比较简单，操作起来也比较容易，从事从“傀儡”节点开始，“傀儡”节点的下一个元素就是队列的头部，前一个元素是队列的尾部，换句话说，“傀儡”节点在头部和尾部之间建立了一个通道，是整个队列形成一个循环，这样就可以从任意一个节点的任意一个方向能遍历完整的队列。
同样LinkedList也是一个没有容量限制的队列，因此入队列(不管是从头部还是尾部)总能成功。
上面描述的ArrayDeque和LinkedList是两种不同方式的实现，通常在遍历和节省内存上ArrayDeque更高效(索引更快，另外不需要Entry对象)，但是在队列扩容下LinkedList更灵活，因为不需要复制原始的队列，某些情况下可能更高效。
同样需要注意的上述两个实现都不是线程安全的，因此只适合在单线程环境下使用，下面章节要介绍的LinkedBlockingDeque就是线程安全的可阻塞的Deque。事实上也应该是功能最强大的Queue实现，当然了实现起来也许会复杂一点。
分享到：
相关推荐
主要介绍了Python collections中的双向队列deque简单介绍详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
在实际使用中，还可以有输出受限的双向队列（即一个端点允许插入和删除，另一个端点只允许插入的双向队列）和输入受限的双向队列（即一个端点允许插入和删除，另一个端点只允许删除的双向队列）。而如果限定双向队列...
主要为大家详细介绍了C++ STL入门教程第三篇，deque双向队列的使用方法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
ArrayDeque 是Java中的双向队列（deque）实现，它基于数组实现并可以高效地在两端进行插入和删除操作。 以下是关于 ArrayDeque 的一些重要信息： 双向队列特性：ArrayDeque 支持在队列的两端进行元素的插入和删除...
本文实例讲述了python3 deque 双向队列创建与使用方法。分享给大家供大家参考，具体如下： 创建双向队列 import collections d = collections.deque() append(往右边添加一个元素) import collections d = ...
双端队列Deque及Python实现双端队列Deque双端队列Deque的Python实现双端队列Deque的应用：“回文词”判断 双端队列Deque 与队列类似，双端队列有两个人口，不同之处在于双端队列的两个口都既可以是入口也可以是出口...
双端队列,在基础类上派生 用来实现平移递推滤波数据存储
python--双端队列deque（csdn）————程序
双端队列（deque，double-ended queue），是一种具有队列和栈的性质的数据结构。 双端队列中每一端，都可以进行存入和取出，去其中一段，都像一个栈一样。 存取也只限定在两端，不能在中间 双端队列的实现 通过...
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点（哨兵） protected DLNode trailer;//指向尾节点（哨兵） protected ...
在Python文档中搜索队列（queue）会发现，Python标准库中包含了四种队列，分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque。 collections.deque deque是双端队列（double-ended ...
分享给大家供大家参考，具体如下： 队列是一种线性表，按照先进先出的原则进行的： 入队： ...什么是双端队列(或双向队列)Deque，全名double-ended queue？ 即元素可以在队列的任意一段入队或出队，
双端队列（Deque） 循环队列 哈希表（HashTable） 树形数据结构 二叉树（BinaryTree）、二叉搜索树（BinarySearchTree、BST） 平衡二叉搜索树（BalancedBinarySearchTree、BBST） AVL树（AVLTree）、红黑树...
* 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点（哨兵） protected DLNode trailer;//指向尾节点（哨兵） protected ...
双向顺序栈的一个常见应用是实现双端队列（deque），即可以在两端进行插入和删除操作的队列。通过在头部和尾部进行入栈和出栈操作，可以方便地实现队列的各种操作，如队列的插入、删除和访问等。