队列

1. 普通队列（Queue）

• 定义：遵循 FIFO（先进先出） 原则的线性表，元素从队尾入队，从队头出队。

• 性质：

  • 基本操作：enqueue()（入队）、dequeue()（出队）、peek()（查看队头）。
  • 不支持随机访问，仅允许在两端操作。
  • 实现方式：数组或链表。

• 实例：

  class Queue<T> {
      private LinkedList<T> list = new LinkedList<>();
      
      public void enqueue(T item) {
          list.addLast(item);
      }
      
      public T dequeue() {
          return list.removeFirst();
      }
      
      public T peek() {
          return list.getFirst();
      }
  }
  

2. 双端队列（Deque）

• 定义：支持在两端插入和删除元素的队列，简称Deque（发音 deck）。

• 性质：

  • 操作灵活：addFirst()、addLast()、removeFirst()、removeLast()。
  • 可模拟栈（LIFO）和队列（FIFO）。
  • 实现方式：数组（如 ArrayDeque）或链表（如 LinkedList）。

• 实例：

  import java.util.Deque;
  import java.util.ArrayDeque;
  
  Deque<Integer> deque = new ArrayDeque<>();
  deque.addFirst(1);    // 队头插入：[1]
  deque.addLast(2);     // 队尾插入：[1, 2]
  int first = deque.removeFirst(); // 移除队头：1
  int last = deque.removeLast();   // 移除队尾：2
  

3. 并发队列（Concurrent Queue）

• 定义：线程安全的队列，允许多个线程无阻塞地并发访问。

• 性质：

  • 基于CAS（Compare-And-Swap）**或**无锁算法实现。
  • 适用于高并发场景（如生产者 - 消费者模式）。
  • Java 实例：ConcurrentLinkedQueue。

• 实例：

  import java.util.concurrent.ConcurrentLinkedQueue;
  
  ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
  // 线程安全的入队
  queue.offer(1);  // 等价于 add()，但返回布尔值
  // 线程安全的出队
  Integer item = queue.poll();  // 队列为空时返回 null
  

4. 阻塞队列（Blocking Queue）

• 定义：当队列为空时，出队操作会被阻塞；当队列满时，入队操作会被阻塞。

• 性质：

  • 支持阻塞操作：put()（入队，满则阻塞）、take()（出队，空则阻塞）。
  • 常用于线程间协作（如线程池、消息队列）。
  • Java 实例：ArrayBlockingQueue、LinkedBlockingQueue。

• 实例：

  import java.util.concurrent.ArrayBlockingQueue;
  
  ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
  // 入队（队列满时阻塞）
  queue.put(1);
  // 出队（队列空时阻塞）
  Integer item = queue.take();
  

对比总结

相互转换

普通队列 → 双端队列：

直接使用 Deque 接口的实现类（如 ArrayDeque），并限制只调用队尾入队、队头出队的方法。

Deque<Integer> deque = new ArrayDeque<>();
deque.addLast(1);  // 入队
Integer item = deque.removeFirst();  // 出队

普通队列 → 并发队列：

使用 ConcurrentLinkedQueue 替换普通队列实现，操作接口不变。

Queue<Integer> queue = new ConcurrentLinkedQueue<>();

普通队列 → 阻塞队列：

使用 ArrayBlockingQueue 或 LinkedBlockingQueue 替换，需处理阻塞异常。

BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
try {
    queue.put(1);  // 可能阻塞
    Integer item = queue.take();  // 可能阻塞
} catch (InterruptedException e) {
    Thread.currentThread().interrupt();
}

双端队列 → 并发双端队列：

使用 ConcurrentLinkedDeque 实现线程安全的双端操作。

import java.util.concurrent.ConcurrentLinkedDeque;

ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();
deque.addFirst(1);  // 线程安全的队头插入

总结

相同点：

均为线性表，支持元素的有序存储和访问。

不同点：

主要区别在于操作限制、线程安全性和阻塞特性，需根据场景选择。

转换原则：

低功能队列可通过高功能队列的接口限制实现（如用 Deque 模拟 Queue），但反之需额外处理并发或阻塞逻辑。

注：实际应用中，优先使用 Java 标准库提供的实现（如 ArrayDeque、ConcurrentLinkedQueue），避免自行实现并发控制。