Java Deque 接口详解

Jakob Jenkov 2020-05-04

Java 的 Deque 接口（java.util.Deque）表示一个双端队列（Double Ended Queue），即可以从队列的两端添加和删除元素。Deque 是 “Double Ended Queue” 的缩写，发音为 “deck”（与“一副牌 deck of cards”中的 deck 相同）。

由于你可以在 Deque 的两端进行入队（enqueue）和出队（dequeue）操作，因此 Deque 既可以当作队列（Queue）使用，也可以当作栈（Stack）使用。

Java 的 Deque 接口继承自 Queue 接口，这意味着在使用 Deque 时，你可以调用所有 Queue 接口定义的方法。虽然 Deque 并没有继承 Stack 类，但它定义了可用于实现栈操作的方法（如 push、peek、pop）。

Deque 的实现类

由于 Deque 是一个接口，要使用它，你需要实例化一个具体的实现类。Java 集合框架中提供了以下两种常用的 Deque 实现：

java.util.LinkedList
java.util.ArrayDeque
LinkedList：内部使用链表结构实现队列或双端队列，是一种标准的 Deque 和 Queue 实现。
ArrayDeque：内部使用数组存储元素。当元素数量超过当前数组容量时，会自动分配一个更大的新数组，并将原有元素迁移过去。也就是说，尽管底层是数组，但 ArrayDeque 会根据需要动态扩容。

创建 Deque 实例

在使用 Deque 之前，必须先创建其实现类的实例：

Deque deque = new LinkedList();

或者：

Deque deque = new ArrayDeque();

泛型 Deque

默认情况下，你可以向 Deque 中添加任意 Object 对象。但通过使用 Java 泛型，可以限制 Deque 中元素的类型。例如：

Deque<MyObject> deque = new LinkedList<MyObject>();

这样，该 Deque 只能插入 MyObject 类型的实例。在访问或遍历时，也无需进行强制类型转换：

MyObject myObject = deque.remove();

for (MyObject anObject : deque) {
    // 对 anObject 执行操作...
}

最佳实践：声明 Deque 变量时始终指定泛型类型。这样编译器可以帮你检查插入的元素类型，避免运行时类型错误，同时提高代码可读性。

更多关于泛型的信息，请参阅 Java 泛型教程。

向 Deque 添加元素

如前所述，你可以在 Deque 的头部（首端）或尾部（末端）添加元素。Deque 接口提供了以下方法：

add()
addLast()
addFirst()
offer()
offerFirst()
offerLast()
push()

`add()`

将元素添加到 Deque 的尾部（等同于队列入队）：

Deque<String> deque = new ArrayDeque<>();
deque.add("element 1");

如果插入失败（例如队列已满），add() 会抛出异常。这与 offer() 不同，后者在失败时返回 false。

注意：add() 方法继承自 Queue 接口。

`addLast()`

与 add() 功能相同，显式地将元素添加到尾部：

deque.addLast("element 1");

插入失败时抛出异常（不同于 offerLast() 返回 false）。

`addFirst()`

将元素添加到 Deque 的头部：

deque.addFirst("element 1");

失败时抛出异常（不同于 offerFirst() 返回 false）。

`offer()`

将元素添加到尾部，成功返回 true，失败（如队列满）返回 false：

deque.offer("element 1");

`offerLast()`

功能与 offer() 相同，但命名更明确：

deque.offerLast("element 1");

`offerFirst()`

将元素添加到头部，成功返回 true，失败返回 false：

deque.offerFirst("element 1");

`push()`

将元素压入 Deque 的头部（用于模拟栈的 push 操作）：

Deque<String> deque = new LinkedList<>();
deque.push("element 0");

如果插入失败（如空间不足），会抛出异常，行为类似于 addFirst()。

查看（Peek）Deque 中的元素

“Peek” 指的是查看但不移除元素。Deque 提供以下方法：

peek()
peekFirst()
peekLast()
getFirst()
getLast()

`peek()`

返回头部的第一个元素，若 Deque 为空则返回 null：

String firstElement = deque.peek(); // "first element"

`peekFirst()`

与 peek() 相同，但语义更清晰：

String firstElement = deque.peekFirst();

`peekLast()`

返回尾部的最后一个元素，为空时返回 null：

String lastElement = deque.peekLast(); // "last element"

`getFirst()`

返回头部元素，若为空则抛出异常（不同于 peek()）：

String firstElement = deque.getFirst();

`getLast()`

返回尾部元素，若为空则抛出异常：

String lastElement = deque.getLast();

从 Deque 中移除元素

移除元素的方法包括：

remove()
removeFirst()
removeLast()
poll()
pollFirst()
pollLast()
pop()

`remove()`

移除并返回头部元素（继承自 Queue）。若为空则抛出异常：

String removedElement = deque.remove();

`removeFirst()`

移除头部元素，为空时抛出异常：

String removedElement = deque.removeFirst();

`removeLast()`

移除尾部元素，为空时抛出异常：

String removedElement = deque.removeLast(); // "element 2"

`poll()`

移除头部元素，为空时返回 null（安全操作）：

String removedElement = deque.poll();

`pollFirst()`

与 poll() 相同，语义更明确：

String removedElement = deque.pollFirst();

`pollLast()`

移除尾部元素，为空时返回 null：

String removedElement = deque.pollLast();

`pop()`

从头部弹出元素（模拟栈的 pop 操作），为空时抛出异常：

Deque<String> deque = new LinkedList<>();
deque.push("element 0");
String removedElement = deque.pop();

行为与 removeFirst() 相同。

检查 Deque 是否包含某元素

使用 contains() 方法：

boolean containsElement1 = deque.contains("first element"); // true
boolean containsElement2 = deque.contains("second element"); // false

获取 Deque 的大小

使用 size() 方法：

int size = deque.size(); // 2

遍历 Deque 中的元素

你可以一次性遍历所有元素，而非逐个处理。有两种方式：

1. 使用 Iterator

Iterator<String> iterator = deque.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    // 处理 element
}

2. 使用 for-each 循环

for (String element : deque) {
    System.out.println(element);
}

注意：遍历顺序取决于具体的 Deque 实现（如 LinkedList 按插入顺序，ArrayDeque 也是从头到尾），但遍历语法是通用的。

Java Deque 接口详解

Deque 的实现类

创建 Deque 实例

泛型 Deque

向 Deque 添加元素

add()

addLast()

addFirst()

offer()

offerLast()

offerFirst()

push()

查看（Peek）Deque 中的元素

peek()

peekFirst()

peekLast()

getFirst()

getLast()