java Queue 详解

Java `Queue` 详解

Queue 是 Java 集合框架中用于实现队列数据结构的接口，位于 java.util 包中。队列是一种 先进先出（FIFO） 的数据结构，元素按照插入的顺序依次出队。

1. Queue 的基本特性

FIFO（First-In-First-Out）：
- 队列中的第一个元素是最先被处理的。
- 特殊实现（如 Deque）可以支持双向队列操作。
队列操作：
- 插入元素：add() / offer()。
- 访问元素（不移除）：element() / peek()。
- 移除元素：remove() / poll()。
接口定义：
Queue 是一个接口，继承自 java.util.Collection。
实现类：
- LinkedList（常用）
- PriorityQueue
- ArrayDeque
- ConcurrentLinkedQueue（线程安全）

2. Queue 的方法

Queue 接口提供了以下主要方法：

方法	描述
`add(E e)`	将指定元素插入队列，如果队列已满，则抛出异常。
`offer(E e)`	将指定元素插入队列，如果队列已满，则返回 `false`。
`remove()`	移除并返回队列头部的元素，如果队列为空，则抛出异常。
`poll()`	移除并返回队列头部的元素，如果队列为空，则返回 `null`。
`element()`	返回队列头部的元素（不移除），如果队列为空，则抛出异常。
`peek()`	返回队列头部的元素（不移除），如果队列为空，则返回 `null`。

方法对比

方法类型	抛出异常	返回特殊值
插入	`add()`	`offer()`
移除	`remove()`	`poll()`
访问（不移除）	`element()`	`peek()`

3. Queue 的实现类

3.1 LinkedList

LinkedList 是 Queue 的常用实现之一，底层基于链表实现。
它既可以用作队列（FIFO），也可以用作双向队列（Deque）。

示例：

import java.util.LinkedList;
import java.util.Queue;public class LinkedListQueue {public static void main(String[] args) {Queue<String> queue = new LinkedList<>();// 添加元素queue.add("A");queue.add("B");queue.add("C");// 访问头部元素System.out.println("Head: " + queue.peek()); // 输出：A// 移除元素System.out.println("Removed: " + queue.poll()); // 输出：A// 遍历队列for (String item : queue) {System.out.println(item); // 输出：B, C}}
}

3.2 PriorityQueue

基于 堆（Heap） 实现的队列，元素按照自然顺序或自定义顺序排序。
特点：
- 不保证 FIFO 顺序，优先级高的元素先出队。
- 适合实现优先级任务调度。

示例：

import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {PriorityQueue<Integer> pq = new PriorityQueue<>();// 添加元素pq.add(5);pq.add(2);pq.add(8);pq.add(1);// 按优先级移除元素while (!pq.isEmpty()) {System.out.println(pq.poll()); // 输出：1, 2, 5, 8}}
}

注意：PriorityQueue 不支持 null 元素。

3.3 ArrayDeque

基于 动态数组 实现的双端队列（Deque）。
特点：
- 比 LinkedList 更高效（无额外的链表节点开销）。
- 可以用作栈（LIFO）或队列（FIFO）。

示例：

import java.util.ArrayDeque;
import java.util.Queue;public class ArrayDequeExample {public static void main(String[] args) {Queue<String> queue = new ArrayDeque<>();// 添加元素queue.offer("X");queue.offer("Y");queue.offer("Z");// 访问头部元素System.out.println("Head: " + queue.peek()); // 输出：X// 移除元素System.out.println("Removed: " + queue.poll()); // 输出：X}
}

3.4 ConcurrentLinkedQueue

是一个线程安全的非阻塞队列，基于 CAS（Compare-And-Swap） 实现。
适用场景：
- 适用于高并发场景下的无界队列。

示例：

import java.util.concurrent.ConcurrentLinkedQueue;public class ConcurrentQueueExample {public static void main(String[] args) {ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();// 添加元素queue.offer("P");queue.offer("Q");queue.offer("R");// 访问头部元素System.out.println("Head: " + queue.peek()); // 输出：P// 移除元素System.out.println("Removed: " + queue.poll()); // 输出：P}
}

4. 特殊队列

4.1 阻塞队列（BlockingQueue）

提供阻塞操作的队列接口，位于 java.util.concurrent 包中。
主要实现类：
- ArrayBlockingQueue：基于数组的有界阻塞队列。
- LinkedBlockingQueue：基于链表的阻塞队列。
- PriorityBlockingQueue：支持优先级排序的阻塞队列。
- SynchronousQueue：一个没有存储能力的队列，直接在生产者和消费者之间传递数据。

示例：

import java.util.concurrent.ArrayBlockingQueue;public class BlockingQueueExample {public static void main(String[] args) throws InterruptedException {ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(3);// 添加元素queue.put("1");queue.put("2");queue.put("3");// 移除元素System.out.println(queue.take()); // 输出：1}
}

特点：

当队列满时，插入操作会阻塞。
当队列空时，删除操作会阻塞。

4.2 双端队列（Deque）

是 Queue 的子接口，支持从两端插入和删除元素。
常见实现：
- ArrayDeque
- LinkedList

示例：

import java.util.Deque;
import java.util.LinkedList;public class DequeExample {public static void main(String[] args) {Deque<String> deque = new LinkedList<>();// 添加元素deque.addFirst("A");deque.addLast("B");// 访问头尾元素System.out.println("First: " + deque.getFirst()); // 输出：ASystem.out.println("Last: " + deque.getLast());   // 输出：B// 移除元素deque.removeFirst();System.out.println("After removing first: " + deque);}
}

5. Queue 的常见用例

5.1 任务调度

使用 PriorityQueue 或 BlockingQueue 实现任务调度。

5.2 消息队列

使用 ConcurrentLinkedQueue 或 BlockingQueue 实现线程间通信。

5.3 树/图的广度优先搜索（BFS）

使用 Queue 存储待访问的节点。

示例：

import java.util.LinkedList;
import java.util.Queue;public class BFSExample {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();// 初始化队列queue.offer(1);while (!queue.isEmpty()) {int node = queue.poll();System.out.println("Visited node: " + node);// 模拟添加邻居节点if (node < 3) {queue.offer(node + 1);}}}
}

输出：

Visited node: 1
Visited node: 2
Visited node: 3

6. 总结

常用实现类对比

实现类	特点	适用场景
`LinkedList`	基于链表，支持双端队列操作；性能适中。	一般队列操作或双向队列。
`PriorityQueue`	元素按优先级排序，不保证 FIFO 顺序。	优先级任务调度。
`ArrayDeque`	高效实现队列和栈；比 `LinkedList` 更节省内存。	双端队列或栈的实现。
`ConcurrentLinkedQueue`	线程安全的无界队列，适用于高并发场景。	多线程环境下的队列操作。
`BlockingQueue`	提供阻塞操作，用于线程间通信。	生产者-消费者模式。