Java Queue
详解
Queue
是 Java 集合框架中用于实现 队列 数据结构的接口,位于 java.util
包中。队列是一种 先进先出(FIFO) 的数据结构,元素按照插入的顺序依次出队。
1. Queue 的基本特性
-
FIFO(First-In-First-Out):
-
队列操作:
- 插入元素:
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
示例:
java">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 顺序,优先级高的元素先出队。
- 适合实现优先级任务调度。
示例:
java">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
示例:
java">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
示例:
java">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">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
示例:
java">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
存储待访问的节点。
示例:
java">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 | 提供阻塞操作,用于线程间通信。 | 生产者-消费者模式。 |
选择 Queue
实现时,应根据具体需求(如是否需要优先级、线程安全等)选择合适的实现类。