双端队列实现

Deque接口，发音为"deck"，表示双端队列。可以将Deque接口实现为各种类型的Collections。将Deque接口的实现分为通用和并发两种。

通用的Deque实现

通用的实现包括LinkedList和ArrayDeque类。 Deque接口支持在两端插入、删除和检索元素。 ArrayDeque类是Deque接口的可调整大小的数组实现，而LinkedList类是列表实现。

Deque接口的基本插入、删除和检索操作包括addFirst、addLast、removeFirst、removeLast、getFirst和getLast方法。 addFirst方法在头部添加元素，而addLast方法在尾部添加元素。

LinkedList实现比ArrayDeque实现更灵活。 LinkedList实现了所有可选的列表操作。 LinkedList实现允许null元素，而ArrayDeque实现不允许。

在效率方面，ArrayDeque在两端的添加和删除操作上比LinkedList更高效。 LinkedList实现中最好的操作是在迭代过程中删除当前元素。 LinkedList实现不适合迭代。

LinkedList实现比ArrayDeque实现消耗更多内存。 对于ArrayDeque实例遍历，请使用以下任意一种方法：

foreach

foreach循环快速且可用于各种类型的列表。

ArrayDeque<String> aDeque = new ArrayDeque<String>();

. . .
for (String str : aDeque) {
    System.out.println(str);
}

Iterator

Iterator可用于所有类型的列表的正向遍历和各种类型的数据。

ArrayDeque<String> aDeque = new ArrayDeque<String>();
. . .
for (Iterator<String> iter = aDeque.iterator(); iter.hasNext();  ) {
    System.out.println(iter.next());
}

本教程中使用ArrayDeque类来实现Deque接口。本教程中使用的示例的完整代码可在ArrayDequeSample中找到。 LinkedList和ArrayDeque类都不支持多线程的并发访问。

并发Deque实现

LinkedBlockingDeque类是Deque接口的并发实现。如果双端队列为空，则takeFirst和takeLast等方法会等待，直到元素可用，然后检索并删除该元素。