java栈和队列 双端队列

### Java双端队列Deque的实现与使用 #### 1. 接口定义与继承关系 `Deque` 是 `java.util` 包中的一个接口，表示双端队列（Double-ended Queue），支持在队列两端进行元素的插入和移除操作。该接口继承自 `Queue` 接口，并扩展了其功能[^2]。 #### 2. 常见实现类 `Deque` 的主要实现类包括： - **ArrayDeque**: 基于数组的双端队列，性能较高，适合大多数场景。 - **LinkedList**: 虽然常被用作链表，但也实现了 `Deque` 接口，能够充当双端队列。 - **LinkedBlockingDeque**: 提供线程安全的支持，在多线程环境中常用[^3]。 #### 3. 主要方法 以下是 `Deque` 接口中的一些核心方法及其作用： | 方法名 | 描述 | |-------------------|----------------------------------------------------------------------| | `addFirst(E e)` | 将指定元素插入到此双端队列的开头。 | | `addLast(E e)` | 将指定元素插入到此双端队列的结尾。 | | `offerFirst(E e)` | 尝试将指定元素插入到此双端队列的开头（可选操作）。 | | `offerLast(E e)` | 尝试将指定元素插入到此双端队列的结尾（可选操作）。 | | `removeFirst()` | 移除此双端队列的第一个元素并返回它；如果为空则抛出异常。 | | `removeLast()` | 移除此双端队列的最后一个元素并返回它；如果为空则抛出异常。 | | `pollFirst()` | 获取并移除此双端队列的第一个元素；如果为空则返回 null。 | | `pollLast()` | 获取并移除此双端队列的最后一个元素；如果为空则返回 null。 | | `peekFirst()` | 返回第一个元素而不移除它；如果为空则返回 null。 | | `peekLast()` | 返回最后一个元素而不移除它；如果为空则返回 null。 | 这些方法使得 `Deque` 成为了一个多用途的数据结构[^1]。 #### 4. 使用示例 以下是一些常见的 `Deque` 使用案例： ##### (1) 创建双端队列 可以通过不同的实现类创建 `Deque` 对象： ```java // 使用 ArrayDeque 创建双端队列 Deque<Integer> arrayDeque = new ArrayDeque<>(); // 使用 LinkedList 创建双端队列 Deque<Integer> linkedListDeque = new LinkedList<>(); ``` ##### (2) 添加元素 向双端队列的头部或尾部添加元素： ```java arrayDeque.addFirst(1); // 向头部添加元素 arrayDeque.addLast(2); // 向尾部添加元素 ``` ##### (3) 删除元素 从双端队列的头部或尾部删除元素： ```java Integer firstElement = arrayDeque.removeFirst(); // 删除并获取头部元素 Integer lastElement = arrayDeque.pollLast(); // 删除并获取尾部元素（可能返回 null） ``` ##### (4) 查看元素 查看但不移除双端队列的头或尾元素： ```java Integer peekFirst = arrayDeque.peekFirst(); // 查看头部元素 Integer peekLast = arrayDeque.peekLast(); // 查看尾部元素 ``` ##### (5) 替代 Stack 功能 由于 `Deque` 支持栈的操作方法 (`push`, `pop`, `peek`)，可以用它替代传统的 `Stack` 类： ```java Deque<String> stack = new ArrayDeque<>(); stack.push("A"); // 元素入栈 String top = stack.pop(); // 元素出栈 String peekTop = stack.peek(); // 查看栈顶元素 ``` #### 5. 特殊用途 除了基本的队列功能外，`Deque` 还可以用于模拟其他数据结构的行为： - **普通队列**：仅在一端插入、另一端取出元素。 - **双向队列**：可以在两端自由插入和移除元素。 - **栈**：通过 `push/pop/peek` 操作实现 LIFO 行为[^4]。 --- ###