当前位置：首页 > article >正文

深入 Java 的 Queue 容器

article 2025/3/7 7:30:46

Java 的 Queue 接口是集合框架中用于处理队列操作的重要部分。它支持在一端插入元素、在另一端删除元素的单端队列，通常遵循“先进先出”（FIFO）规则。本文将介绍 Queue 接口及其扩展 Deque，并探讨常见的实现类：ArrayDeque、LinkedList 和 PriorityQueue。
在这里插入图片描述

Queue 接口

定义

Queue 接口继承自 Collection：

public interface Queue<E> extends Collection<E> {}

特性

Queue 是一个单端队列，操作遵循 FIFO。根据容量限制导致操作失败时的处理方式，Queue 提供了两组方法：

操作	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

抛出异常：适合需要明确失败通知的场景。
返回特殊值：更灵活，失败时返回 null 或 false。

AbstractQueue 抽象类

AbstractQueue 为 Queue 接口提供了核心实现，减少开发者自定义实现的工作量：

public abstract class AbstractQueue<E> extends AbstractCollection<E> implements Queue<E> {}

Deque 接口

定义

Deque（Double Ended Queue，双端队列）继承自 Queue，支持在队列两端插入和删除元素：

public interface Deque<E> extends Queue<E> {}

特性

Deque 扩展了 Queue，增加了双端操作方法，同样分为抛异常和返回特殊值两类：

操作	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

此外，Deque 还支持 push() 和 pop()，可模拟栈的行为。它既支持有容量限制的队列，也支持无限制的实现。

ArrayDeque：高效数组实现

概述

ArrayDeque 是 Deque 的顺序表实现，使用动态数组支持队列和栈操作。

特性

底层结构：基于可变长数组和双指针。
不支持 null：不允许存储 null 值。
性能：插入操作均摊时间复杂度为 O(1)，尽管可能涉及扩容。
非线程安全：需外部同步。

使用场景

ArrayDeque 适合高效的队列或栈操作，例如任务调度。

LinkedList：链表实现

概述

LinkedList 是 Deque 的链表实现，支持双端操作。

示例代码

Queue<String> queue = new LinkedList<>();
queue.offer("a"); // 入队
queue.offer("b");
queue.offer("c");
System.out.println("poll=" + queue.poll()); // 出队，返回 "a"
System.out.println("peek=" + queue.peek()); // 查看队首，返回 "b"

与 ArrayDeque 的区别

底层结构：LinkedList 使用链表，ArrayDeque 使用数组。
null 支持：LinkedList 允许 null，ArrayDeque 不允许。
引入时间：LinkedList（JDK 1.2）早于 ArrayDeque（JDK 1.6）。
性能：ArrayDeque 均摊 O(1) 更快，LinkedList 因每次插入需分配堆空间稍慢。

使用场景

LinkedList 适合需要动态调整大小且允许 null 的场景，但性能不如 ArrayDeque。

PriorityQueue：优先级队列

定义

PriorityQueue 是 JDK 1.5 引入的无界优先级队列，元素按优先级出队：

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {}

特性

排序：默认自然顺序（小顶堆），可通过 Comparator 自定义。
不支持 null：拒绝 null 值。
底层结构：基于二叉堆，使用动态数组存储。
性能：插入和删除堆顶元素为 O(log n)。
非线程安全：需同步处理。

使用场景

适合优先级调度场景，如任务按重要性排序执行。

ArrayDeque vs. LinkedList vs. PriorityQueue

特性	ArrayDeque	LinkedList	PriorityQueue
底层结构	动态数组	链表	二叉堆（数组）
顺序	FIFO	FIFO	优先级
null 支持	不支持	支持	不支持
性能	O(1) 均摊	O(1) 但稍慢	O(log n)
场景	高效队列/栈	灵活队列	优先级调度