java Deque 详解

在 Java 中，Deque（双端队列）是一个支持在两端插入和删除的队列。它是 Java Collections Framework 的一部分，通过接口和实现类提供了高效的双端操作能力。

Deque 基础概念

Deque 是 双端队列，支持在队列的头部和尾部添加、删除、访问元素。
它继承自 Queue 接口，是一种更加通用的数据结构。
既可以用作 队列（FIFO），也可以用作 栈（LIFO）。

接口定义

Deque 是一个接口，常用实现类有：

ArrayDeque：基于动态数组的双端队列实现。
LinkedList：基于双向链表的双端队列实现。

常见操作分类

头部操作：addFirst、removeFirst、getFirst
尾部操作：addLast、removeLast、getLast
通用队列操作：offer、poll、peek

Deque 的方法详解

1. 添加元素

在头部添加：
- void addFirst(E e)：在队列头部插入元素，若队列满则抛出异常。
- boolean offerFirst(E e)：在队列头部插入元素，若队列满返回 false。
在尾部添加：
- void addLast(E e)：在队列尾部插入元素，若队列满则抛出异常。
- boolean offerLast(E e)：在队列尾部插入元素，若队列满返回 false。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // 在头部添加
deque.addLast(2);  // 在尾部添加
System.out.println(deque); // 输出：[1, 2]

2. 删除元素

从头部删除：
- E removeFirst()：删除并返回头部元素，若队列为空则抛出异常。
- E pollFirst()：删除并返回头部元素，若队列为空返回 null。
从尾部删除：
- E removeLast()：删除并返回尾部元素，若队列为空则抛出异常。
- E pollLast()：删除并返回尾部元素，若队列为空返回 null。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst(); // 删除头部元素
deque.removeLast();  // 删除尾部元素
System.out.println(deque); // 输出：[]

3. 访问元素

访问头部元素：
- E getFirst()：获取但不删除头部元素，若队列为空则抛出异常。
- E peekFirst()：获取但不删除头部元素，若队列为空返回 null。
访问尾部元素：
- E getLast()：获取但不删除尾部元素，若队列为空则抛出异常。
- E peekLast()：获取但不删除尾部元素，若队列为空返回 null。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);

System.out.println(deque.getFirst()); // 输出：1
System.out.println(deque.getLast());  // 输出：2

4. 栈操作（LIFO）

void push(E e)：将元素压入栈顶（相当于 addFirst）。
E pop()：移除并返回栈顶元素（相当于 removeFirst）。

示例：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 压入栈顶
stack.push(2);
System.out.println(stack.pop()); // 弹出栈顶元素，输出：2
System.out.println(stack.pop()); // 输出：1

5. 队列操作（FIFO）

boolean offer(E e)：将元素添加到队列尾部（相当于 offerLast）。
E poll()：移除并返回队列头部元素（相当于 pollFirst）。
E peek()：获取但不删除队列头部元素（相当于 peekFirst）。

示例：

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 添加到尾部
queue.offer(2);
System.out.println(queue.poll()); // 移除头部元素，输出：1
System.out.println(queue.peek()); // 获取头部元素，输出：2

6. 删除所有元素

void clear()：清空队列。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.add(1);
deque.add(2);
deque.clear(); // 清空队列
System.out.println(deque.isEmpty()); // 输出：true

7. 检查队列状态

boolean isEmpty()：检查队列是否为空。
int size()：返回队列中元素的数量。

Deque 的实现类

1. ArrayDeque

基于动态数组实现。
特点：
- 适合用作栈和队列。
- 线程不安全，但效率较高。
- 不允许存储 null 元素。

示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque); // 输出：[1, 2]

2. LinkedList

基于双向链表实现。
特点：
- 支持队列和栈操作。
- 允许存储 null 元素。
- 适合频繁插入和删除操作的场景。

示例：

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque); // 输出：[1, 2]

常见应用场景

1. 栈实现（LIFO 模式）

Deque 提供了 push 和 pop 方法，可以方便地模拟栈。

示例：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 输出：2
System.out.println(stack.pop()); // 输出：1

2. 队列实现（FIFO 模式）

Deque 提供了 offer 和 poll 方法，可以模拟队列操作。

示例：

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
System.out.println(queue.poll()); // 输出：1
System.out.println(queue.poll()); // 输出：2

3. 滑动窗口

Deque 可以用作维护滑动窗口的数据结构，例如最大值或最小值的计算。

4. 双端处理

Deque 支持从两端同时处理数据，例如支持同时从头尾访问元素的算法（如回文检查）。

总结

方法分类	常用方法	描述
添加元素	`addFirst`、`addLast`、`offer`	向头部或尾部添加元素
删除元素	`removeFirst`、`removeLast`	从头部或尾部删除元素
访问元素	`getFirst`、`getLast`、`peek`	获取头部或尾部元素，但不删除
栈操作	`push`、`pop`	用作栈的 LIFO 操作
队列操作	`offer`、`poll`、`peek`	用作队列的 FIFO 操作
清空队列	`clear`	删除所有元素