跳到主要内容

Java Queue接口

队列简介

在Java集合框架中,Queue(队列)是一种特殊的线性集合,它遵循先进先出(FIFO - First-In-First-Out)的原则,即最先添加的元素最先被移除。Queue接口位于java.util包中,是Collection接口的子接口,主要用于在处理元素前保存元素。

队列的形象比喻就是现实生活中的排队场景:排在队伍最前面的人最先得到服务,新来的人只能排在队尾。

Queue接口的核心方法

Queue接口定义了以下几个核心方法,每个方法的行为在出错/失败情况下有两种不同的表现形式:

操作类型抛出异常的方法返回特殊值的方法
插入add(e)offer(e)
移除remove()poll()
检查element()peek()

方法详解

  1. 插入操作

    • boolean add(E e): 将元素添加到队列,如果队列已满则抛出IllegalStateException
    • boolean offer(E e): 将元素添加到队列,如果成功返回true,队列已满则返回false
  2. 移除操作

    • E remove(): 移除并返回队头元素,如果队列为空则抛出NoSuchElementException
    • E poll(): 移除并返回队头元素,如果队列为空则返回null
  3. 检查操作

    • E element(): 返回队头元素但不移除,如果队列为空则抛出NoSuchElementException
    • E peek(): 返回队头元素但不移除,如果队列为空则返回null
提示

在选择方法时,建议根据你对错误情况的处理需求来决定使用哪一组方法:

  • 如果你希望在操作失败时抛出异常,使用 add/remove/element
  • 如果你希望通过返回值判断操作是否成功,使用 offer/poll/peek

Queue的主要实现类

LinkedList

LinkedList既实现了List接口,也实现了Queue接口。作为队列使用时,它提供了FIFO的队列操作。

java
import java.util.LinkedList;
import java.util.Queue;

public class LinkedListQueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();

// 添加元素
queue.offer("Java");
queue.offer("Python");
queue.offer("C++");

System.out.println("队列: " + queue);

// 访问队列头部元素
System.out.println("队头元素: " + queue.peek());

// 移除元素
String removed = queue.poll();
System.out.println("移除的元素: " + removed);
System.out.println("移除后的队列: " + queue);
}
}

输出:

队列: [Java, Python, C++]
队头元素: Java
移除的元素: Java
移除后的队列: [Python, C++]

PriorityQueue

PriorityQueue是一个基于优先级堆的队列,元素按照自然顺序或者比较器(Comparator)指定的顺序排序。队列头部的元素总是优先级最高(最小)的元素。

java
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个优先队列
Queue<Integer> priorityQueue = new PriorityQueue<>();

// 添加元素
priorityQueue.offer(5);
priorityQueue.offer(1);
priorityQueue.offer(3);
priorityQueue.offer(2);
priorityQueue.offer(4);

System.out.println("优先队列: " + priorityQueue);

// 移除元素(按优先级排序)
while (!priorityQueue.isEmpty()) {
System.out.println("移除: " + priorityQueue.poll());
}
}
}

输出:

优先队列: [1, 2, 3, 5, 4]
移除: 1
移除: 2
移除: 3
移除: 4
移除: 5
备注

注意在上面的例子中,打印整个优先队列时显示的顺序可能看起来不是有序的,这是因为内部堆结构的表示。但是当我们使用poll()方法逐个移除元素时,它们会按照优先级顺序(从小到大)被移除。

ArrayDeque

ArrayDeque是一个基于数组实现的双端队列,它实现了Deque接口,可以作为队列或栈来使用。作为队列使用时,它通常比LinkedList有更好的性能。

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("红");
queue.offer("橙");
queue.offer("黄");

System.out.println("队列: " + queue);

// 移除元素
String removed = queue.poll();
System.out.println("移除的元素: " + removed);
System.out.println("移除后的队列: " + queue);
}
}

输出:

队列: [红, 橙, 黄]
移除的元素: 红
移除后的队列: [橙, 黄]

阻塞队列

Java还提供了BlockingQueue接口,它扩展了Queue接口,主要用于生产者-消费者模式,提供了阻塞的插入和获取操作。当队列满时,插入操作将阻塞;当队列空时,获取操作将阻塞。

主要的实现类有:ArrayBlockingQueueLinkedBlockingQueuePriorityBlockingQueue等。

java
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class BlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
// 创建容量为2的阻塞队列
BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(2);

// 添加元素
blockingQueue.put("元素1");
blockingQueue.put("元素2");
System.out.println("队列已满: " + blockingQueue);

// 启动一个线程消费元素
new Thread(() -> {
try {
Thread.sleep(2000); // 等待2秒
System.out.println("消费者消费: " + blockingQueue.take());
} catch (InterruptedException e) {
e.printStackTrace();
}
}).start();

// 这里会阻塞,直到队列有空间
System.out.println("生产者等待放入元素...");
blockingQueue.put("元素3"); // 阻塞直到有空间
System.out.println("元素3已放入队列: " + blockingQueue);
}
}

输出:

队列已满: [元素1, 元素2]
生产者等待放入元素...
消费者消费: 元素1
元素3已放入队列: [元素2, 元素3]

实际应用场景

Queue在Java编程中有广泛的应用,以下是几个常见的场景:

1. 任务调度系统

在任务调度系统中,待执行的任务可以放入队列,由执行线程按照先来先执行的顺序处理。

java
import java.util.LinkedList;
import java.util.Queue;

class Task {
private String name;

public Task(String name) {
this.name = name;
}

public void execute() {
System.out.println("执行任务: " + name);
}

@Override
public String toString() {
return name;
}
}

public class TaskScheduler {
private Queue<Task> taskQueue = new LinkedList<>();

public void addTask(Task task) {
taskQueue.offer(task);
}

public void processTasks() {
while (!taskQueue.isEmpty()) {
Task task = taskQueue.poll();
task.execute();
}
}

public static void main(String[] args) {
TaskScheduler scheduler = new TaskScheduler();

// 添加任务
scheduler.addTask(new Task("发送邮件"));
scheduler.addTask(new Task("生成报表"));
scheduler.addTask(new Task("数据备份"));

// 处理所有任务
scheduler.processTasks();
}
}

输出:

执行任务: 发送邮件
执行任务: 生成报表
执行任务: 数据备份

2. 广度优先搜索 (BFS)

在图或树的广度优先搜索算法中,通常使用队列来存储待访问的节点。

java
import java.util.*;

class TreeNode {
int value;
TreeNode left;
TreeNode right;

TreeNode(int value) {
this.value = value;
}
}

public class BfsExample {
public static void levelOrderTraversal(TreeNode root) {
if (root == null) return;

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
TreeNode current = queue.poll();

// 处理当前节点
System.out.print(current.value + " ");

// 将子节点加入队列
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
}

public static void main(String[] args) {
// 构建一个简单的二叉树
// 1
// / \
// 2 3
// / \
// 4 5

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

System.out.println("层序遍历结果:");
levelOrderTraversal(root);
}
}

输出:

层序遍历结果:
1 2 3 4 5

3. 消息队列/事件处理

队列常用于实现简单的消息或事件处理系统:

java
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

class Message {
private String content;

public Message(String content) {
this.content = content;
}

public String getContent() {
return content;
}
}

class MessageProducer implements Runnable {
private BlockingQueue<Message> queue;

public MessageProducer(BlockingQueue<Message> queue) {
this.queue = queue;
}

@Override
public void run() {
try {
for (int i = 1; i <= 5; i++) {
Message msg = new Message("消息-" + i);
queue.put(msg);
System.out.println("生产: " + msg.getContent());
Thread.sleep(100);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}

class MessageConsumer implements Runnable {
private BlockingQueue<Message> queue;

public MessageConsumer(BlockingQueue<Message> queue) {
this.queue = queue;
}

@Override
public void run() {
try {
while (true) {
Message msg = queue.take();
System.out.println("消费: " + msg.getContent());
Thread.sleep(300); // 消费速度较慢
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}

public class MessageQueueExample {
public static void main(String[] args) {
BlockingQueue<Message> queue = new LinkedBlockingQueue<>();

new Thread(new MessageProducer(queue)).start();
new Thread(new MessageConsumer(queue)).start();
}
}

输出:

生产: 消息-1
消费: 消息-1
生产: 消息-2
生产: 消息-3
消费: 消息-2
生产: 消息-4
生产: 消息-5
消费: 消息-3
消费: 消息-4
消费: 消息-5

总结

Queue接口是Java集合框架中一个重要的组成部分,它主要用于表示先进先出(FIFO)的数据结构。主要特点如下:

  1. 核心方法:Queue接口定义了插入、移除和检查元素的方法,每种操作都有两个版本(抛出异常和返回特殊值)

  2. 主要实现类

    • LinkedList: 实现基本的FIFO队列
    • PriorityQueue: 按照元素的优先级出队
    • ArrayDeque: 比LinkedList更高效的双端队列实现
    • BlockingQueue: 支持生产者-消费者模式的线程安全队列
  3. 应用场景

    • 任务调度
    • 广度优先搜索算法
    • 消息队列/事件处理
    • 缓冲区管理

在选择具体的队列实现时,需要根据应用场景的特点来决定:

  • 需要优先级排序:PriorityQueue
  • 需要高效的FIFO队列:ArrayDeque
  • 需要阻塞功能:BlockingQueue的实现类
  • 需要双端操作:实现Deque接口的类

练习题

  1. 编写一个程序,使用PriorityQueue实现一个简单的任务优先级调度器,任务有不同的优先级。

  2. 使用ArrayDeque实现一个简单的"撤销"功能,存储用户的最近10个操作,允许用户取消这些操作。

  3. 使用BlockingQueue实现一个多线程的生产者-消费者模式,其中有多个生产者和消费者线程同时运行。

通过这些练习,你可以更好地理解和掌握Java中Queue接口及其各种实现的使用方法和应用场景。

额外学习资源

  • Java官方文档中关于Queue接口的说明
  • Java源码阅读,特别是LinkedList、PriorityQueue和ArrayDeque的实现
  • 深入学习并发编程中的BlockingQueue应用