Deque概述

Deque（全称Double-Ended Queue，双端队列）是一种允许在队列两端（头部和尾部）高效插入和删除元素的线性数据结构。
与普通队列（FIFO）不同，Deque既支持FIFO操作（队尾插入、队头删除），也支持LIFO操作（栈行为：队头插入和删除），因此可同时作为队列和栈使用。

核心特性：

  • 在队列的头部和尾部均可执行插入（add/offer）和删除（remove/poll）操作。
  • 插入和删除操作的时间复杂度通常为O(1)（取决于具体实现）。
  • 线程安全版本需通过Collections.synchronizedDeque包装或使用并发容器（如LinkedBlockingDeque）。

Deque的接口定义（Java中的Deque）

Java中的Deque接口继承自Queue<E>，定义在java.util包中。
主要方法分为四类：头部操作、尾部操作、访问操作和批量操作。

核心方法分类

操作类型 头部操作（Head） 尾部操作（Tail）
插入 void addFirst(E e)：插入到头部，失败抛出IllegalStateException。 void addLast(E e)：插入到尾部，失败抛出IllegalStateException。
boolean offerFirst(E e)：插入到头部，失败返回false（不抛异常）。 boolean offerLast(E e)：插入到尾部，失败返回false（不抛异常）。
删除 E removeFirst()：删除并返回头部元素，队列为空时抛出NoSuchElementException。 E removeLast()：删除并返回尾部元素，队列为空时抛出NoSuchElementException。
E pollFirst()：删除并返回头部元素，队列为空时返回null。 E pollLast()：删除并返回尾部元素，队列为空时返回null。
访问（不删） E getFirst()：返回头部元素，队列为空时抛出NoSuchElementException。 E getLast()：返回尾部元素，队que为空时抛出NoSuchElementException。
E peekFirst()：返回头部元素，队列为空时返回null。 E peekLast()：返回尾部元素，队列为空时返回null。
其他操作 void push(E e)：等效于addFirst(e)（栈行为：压栈）。 E pop()：等效于removeFirst()（栈行为：弹栈）。

Deque的常见实现类

Java提供了多种Deque的实现，根据底层数据结构和线程安全性分为以下几类：

基于数组的可变大小实现

  • ArrayDeque
    • 底层基于动态数组（默认初始容量为16，扩容机制类似ArrayList）。
    • 非线程安全，但性能高（无锁设计）。
    • 特点：
      • 不支持存储null元素（addFirst/addLast传入null会抛出NullPointerException）。
      • 作为栈使用时性能优于Stack类（Stack是线程安全的遗留类，基于Vector，性能较差）。

基于链表的可变大小实现

  • LinkedList
    • 底层基于双向链表。
    • 非线程安全，但插入/删除操作性能高（O(1)时间复杂度）。
    • 特点：
      • 允许存储null元素。
      • 同时实现了List和Deque接口，可作为列表、队列或栈使用。

⚠️ 注意：LinkedList在频繁随机访问时性能较差（需遍历链表），但作为双端队列或栈时效率极高。

线程安全的实现（并发场景）

  • LinkedBlockingDeque
    • 底层基于双向链表，支持有界或无界容量（构造时可指定容量，默认Integer.MAX_VALUE）。
    • 线程安全，内部通过锁机制保证并发操作的原子性。
    • 适用场景：多线程环境下的生产-消费者模型（作为阻塞队列使用）。
## Deque的使用示例

作为队列（FIFO）使用

1
2
3
4
5
6
7
public void a() {
    Deque<String> deque = new ArrayDeque<>();
    deque.addLast("A"); // 队尾插入
    deque.addLast("B");
    String first = deque.removeFirst(); // 队头删除（FIFO）
    System.out.println(first); // 输出: A
}

作为栈（LIFO）使用

1
2
3
4
5
6
7
public void a(){
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(1); // 压栈（等效于addFirst）
    stack.push(2);
    int top = stack.pop(); // 弹栈（等效于removeFirst）
    System.out.println(top); // 输出: 2
}

混合操作（两端插入和删除）

1
2
3
4
5
6
7
8
public void a(){
    Deque<Double> deque = new LinkedList<>();
    deque.addFirst(1.1); // 头部插入
    deque.addLast(2.2);  // 尾部插入
    double head = deque.peekFirst(); // 访问头部（不删除）
    double tail = deque.pollLast();  // 删除尾部（返回被删元素）
    System.out.println(head + ", " + tail); // 输出: 1.1, 2.2
}

Deque与Queue、Stack的关系

Deque与Queue

  1. Queue（队列）：仅支持FIFO操作（add/remove/element对应队尾插入、队头删除）。
  2. Deque：扩展了Queue的功能，支持在双端操作，因此可完全替代Queue（例如用addLast代替add，removeFirst代替remove）。

Deque与Stack

  1. 传统Stack类：仅支持LIFO操作（push/pop/peek），但设计为单端操作，且继承自Vector（线程安全但性能差）。
  2. Deque作为栈：通过push（等效于addFirst）、pop（等效于removeFirst）和peek（等效于peekFirst）实现栈行为，性能更高且代码更简洁（推荐优先使用Deque代替Stack）。