Java Deque接口源码解读和应用

在 Java 中，Deque（Double-Ended Queue，双端队列）接口是 Queue 接口的子接口，允许在队列的两端添加或移除元素。这使得 Deque 既可以表现为 FIFO（先进先出） 队列，也可以表现为 LIFO（后进先出） 栈。Deque 接口位于 java.util 包中，并由常用的实现类如 ArrayDeque 和 LinkedList 提供支持。

一、Deque 接口中的方法

Deque 接口扩展了 Queue 接口，添加了在两端插入、移除和查看元素的方法。每种操作都有两个版本：抛出异常 和 返回特定值。

1. 添加元素的方法

Deque 提供在队列头部和尾部添加元素的方法：

void addFirst(E e)：将元素插入到队列的头部。如果队列已满，则抛出 IllegalStateException 异常。

void addLast(E e)：将元素插入到队列的尾部。如果队列已满，则抛出 IllegalStateException 异常。

boolean offerFirst(E e)：将元素插入到队列的头部。如果队列已满，则返回 false。

boolean offerLast(E e)：将元素插入到队列的尾部。如果队列已满，则返回 false。

区别：addFirst 和 addLast 方法在队列已满时抛出异常，而 offerFirst 和 offerLast 方法返回 false。

2. 移除元素的方法

Deque 提供在队列头部和尾部移除元素的方法：

E removeFirst()：移除并返回队列的头部元素。如果队列为空，则抛出 NoSuchElementException。

E removeLast()：移除并返回队列的尾部元素。如果队列为空，则抛出 NoSuchElementException。

E pollFirst()：移除并返回队列的头部元素。如果队列为空，则返回 null。

E pollLast()：移除并返回队列的尾部元素。如果队列为空，则返回 null。

区别：removeFirst 和 removeLast 方法在队列为空时抛出异常，而 pollFirst 和 pollLast 方法返回 null。

3. 查看元素的方法

Deque 提供在队列头部和尾部查看元素的方法：

E getFirst()：返回队列的头部元素，但不删除。如果队列为空，则抛出 NoSuchElementException。

E getLast()：返回队列的尾部元素，但不删除。如果队列为空，则抛出 NoSuchElementException。

E peekFirst()：返回队列的头部元素，但不删除。如果队列为空，则返回 null。

E peekLast()：返回队列的尾部元素，但不删除。如果队列为空，则返回 null。

区别：getFirst 和 getLast 方法在队列为空时抛出异常，而 peekFirst 和 peekLast 方法返回 null。

4. 栈操作的方法

Deque 还提供了栈操作相关的方法，使其可以作为 LIFO 栈使用：

void push(E e)：将元素推入到队列的头部（即作为栈顶）。

E pop()：移除并返回队列的头部元素（即栈顶元素）。如果队列为空，则抛出 NoSuchElementException。

E peek()：返回队列的头部元素（即栈顶元素）而不删除。如果队列为空，则返回 null。

说明：这些方法的设计使得 Deque 可以作为栈来使用，其中 push 和 pop 的操作与 Deque 的 addFirst 和 removeFirst 相对应。

方法总结

二、应用举例

下面是一个 Deque 接口的示例代码，使用 ArrayDeque 作为其实现：

import java.util.ArrayDeque;

import java.util.Deque;

public class DequeExample {

public static void main(String[] args) {

Deque<Integer> deque = new ArrayDeque<>();

// 在头部和尾部添加元素

deque.addFirst(10);

deque.addLast(20);

deque.offerFirst(5);

deque.offerLast(30);

System.out.println("双端队列元素: " + deque); // 输出: [5, 10, 20, 30]

// 获取头部和尾部元素

System.out.println("头部元素 (getFirst): " + deque.getFirst()); // 输出: 5

System.out.println("尾部元素 (getLast): " + deque.getLast()); // 输出: 30

// 移除头部和尾部元素

System.out.println("移除头部元素 (removeFirst): " + deque.removeFirst()); // 输出: 5

System.out.println("移除尾部元素 (removeLast): " + deque.removeLast()); // 输出: 30

System.out.println("双端队列元素 (移除后): " + deque); // 输出: [10, 20]

// 栈操作

deque.push(50);

System.out.println("双端队列元素 (push 后): " + deque); // 输出: [50, 10, 20]

System.out.println("栈顶元素 (pop): " + deque.pop()); // 输出: 50

System.out.println("双端队列元素 (pop 后): " + deque); // 输出: [10, 20]

}

}

代码输出：

双端队列元素: [5, 10, 20, 30]

头部元素 (getFirst): 5

尾部元素 (getLast): 30

移除头部元素 (removeFirst): 5

移除尾部元素 (removeLast): 30

双端队列元素 (移除后): [10, 20]

双端队列元素 (push 后): [50, 10, 20]

栈顶元素 (pop): 50

双端队列元素 (pop 后): [10, 20]

三、设计思路

Deque 提供了 双端操作 的灵活性，使其可以作为队列或栈使用。

Deque 的方法设计分为抛出异常和返回特定值的版本，使得用户可以根据需求选择合适的操作方式。

由于 Deque 允许在两端进行插入和删除操作，因此在实际使用中，Deque 非常适合实现基于 队列 和 栈 的算法，如 广度优先搜索 和 深度优先搜索。

四、常用实现类

ArrayDeque：基于数组实现，效率高且不允许 null 元素，适合用作栈和队列。

LinkedList：基于链表实现，允许 null 元素，适合需要频繁插入和删除的场景。

最后总结

Deque 接口在 Java 中提供了双端队列的标准化操作，使得用户可以灵活地操作元素的插入和移除位置。Deque 提供的多种方法和异常处理机制，使得它在实现栈、队列及更复杂的数据结构时都能得心应手。