原文地址：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实现，当然了实现起来也许会复杂一点。
分享到：
相关推荐
双向队列，又称为deque（双端队列），是Python等语言中的标准库数据结构，它支持在两端进行插入和删除操作。双向队列的灵活性在于，你可以像对待队列一样在一头添加或移除元素，也可以像对待栈一样在另一头进行操作...
12. 双向队列（Deque）双向队列（Deque）是双端队列，支持在两端进行插入和删除操作。Java中的Deque接口有ArrayDeque作为实现类。例如，可以通过以下方式创建Deque：javaDeque<Integer> deque = new ArrayDeque();...
ArrayDeque 是Java中的双向队列（deque）实现，它基于数组实现并可以高效地在两端进行插入和删除操作。 以下是关于 ArrayDeque 的一些重要信息： 双向队列特性：ArrayDeque 支持在队列的两端进行元素的插入和删除...
双端队列（Deque） 循环队列 哈希表（HashTable） 树形数据结构 二叉树（BinaryTree）、二叉搜索树（BinarySearchTree、BST） 平衡二叉搜索树（BalancedBinarySearchTree、BBST） AVL树（AVLTree）、红黑树...
- **队列（queue）**：先进先出（FIFO）的数据结构，通常基于双端队列（deque）实现。 - **双端队列（deque）**：双端的动态数组，支持两端的插入和删除。 - **优先队列（priority_queue）**：最大堆实现，每次弹出...
Java集合框架还包括Queue（队列）和Deque（双端队列）接口。Queue主要用于先进先出（FIFO）的数据结构，如ArrayDeque和LinkedList可以实现；Deque则扩展了Queue，允许在两端进行插入和删除，适用于栈和队列的场景。 ...
4. **列表和队列**：双向列表（BidirectionalList）支持在列表的头部和尾部添加元素，而双向队列（Deque）则提供了双端操作的能力。 5. **过滤和选择**：FilterList和FilterMap可以根据提供的谓词（Predicate）过滤...
这些操作使 LinkedList 可被用作堆栈（stack）、队列（queue）或双向队列（deque）。ArrayList 类实现了可变大小的数组。它允许所有元素，包括 null。ArrayList 没有同步。size、isEmpty、get、set 方法运行时间为...
- 可用作队列、栈或双向队列。 - 不支持随机访问。 #### 六、ArrayList类 `ArrayList`类也是`List`接口的一种实现，它基于动态数组实现。 - **主要特点**： - 提供随机访问能力。 - 添加和删除操作的成本较高...
Deque 接口的主要特点包括双向操作、队列特性和栈特性。Java 标准库中提供了多个实现了 Deque 接口的类，包括 ArrayDeque 和 LinkedList。 集合是 Java 中的一种重要的数据结构，提供了一种灵活、使用方便的接口和...
- **`Deque`**: 双端队列，支持两端的插入和删除操作。 - **`SortedSet`**: 可排序的集合。 - **`SortedMap`**: 可排序的映射。 - **`ListIterator`**: 提供了对`List`的迭代控制。 #### 4. Collection接口为...
在Java集合框架中，主要有六种核心接口：`Collection`, `Set`, `List`, `Queue`, `Deque`, 和 `Map`。此外，还有五个抽象类以及多个实现类，它们共同构成了Java集合框架的基础。 #### 二、核心接口介绍 1. **`...
Java队列是Java集合框架中的一个关键组成部分，主要用于在多个线程之间同步数据传输或实现异步处理。队列遵循先进先出（FIFO）的原则，即最早添加到队列中的元素将首先被处理。本教程将深入探讨如何在Java中使用队列...
- **Deque**：双端队列，允许在两端进行插入和删除操作。 - **其他实现类**： - **Stack**：继承自`Vector`，模拟栈结构，提供了后进先出（LIFO）的行为。 - **ArrayDeque**：高效的双端队列实现，适合频繁的插入...
ArrayDeque是Deque接口的一个高效实现，可以作为双端队列使用，支持在两端添加和移除元素。 4. **TreeSet与TreeMap** TreeSet基于红黑树实现，保证了集合的排序性。它提供了高效的查找、添加和删除操作。TreeMap...
在实际编程中，栈、链表和队列经常结合使用，比如在实现LRU缓存淘汰策略时，可以利用双端队列（Deque）模拟最近最少使用的数据结构。同时，这些数据结构也是许多高级数据结构（如树、图）的基础，为解决复杂问题提供...
LinkedList是一种以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用。它实现了List、Queue和Deque接口，使其具有多种使用场景。 LinkedList的继承体系中，它继承了AbstractSequentialList和...
- `Deque`：双端队列，支持两端插入和移除元素。 2. **具体实现类**： - `ArrayList`：基于动态数组实现的List，提供O(1)的随机访问速度，但插入和删除操作在非尾部位置时效率较低。 - `LinkedList`：双向链表...
4. `Deque`: 双端队列，支持在两端添加、删除元素，ArrayList和LinkedList都可以实现。 二、集合实现类 1. `ArrayList`: 基于动态数组实现，适合随机访问但插入和删除效率较低。 2. `LinkedList`: 基于双向链表实现...