今天我们来聊聊Java中的队列(Queue)~
队列（Queue）的基本概念
定义队列及其操作原则
队列（Queue）是一种特殊类型的集合，它遵循先进先出（FIFO - First In First Out）原则，这意味着第一个添加到队列的元素将是第一个被移除的元素。
解释FIFO原则
FIFO原则是队列操作的核心。在队列中，元素只能从队尾（rear）添加，从队头（front）移除。这种操作方式确保了先进入队列的元素先被取出。
队列的基本操作
队列的基本操作通常包括：
- Enqueue: 添加一个元素到队列的尾部。
- Dequeue: 移除并返回队列头部的元素。
- Peek: 返回队列头部的元素但不移除它。
- isEmpty: 检查队列是否为空。
案例源码说明
下面是一个简单的队列实现示例，使用Java的LinkedList作为底层数据结构，因为LinkedList提供了高效的添加和移除操作。
import java.util.LinkedList;
public class SimpleQueue<T> {
private LinkedList<T> list = new LinkedList<>();
public void enqueue(T element) {
list.addLast(element);
}
public T dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return list.removeFirst();
}
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
return list.getFirst();
}
public boolean isEmpty() {
return list.isEmpty();
}
public static void main(String[] args) {
SimpleQueue<String> queue = new SimpleQueue<>();
queue.enqueue("Alice");
queue.enqueue("Bob");
queue.enqueue("Charlie");
System.out.println(queue.dequeue()); // 输出: Alice
System.out.println(queue.peek()); // 输出: Bob
System.out.println(queue.dequeue()); // 输出: Bob
System.out.println(queue.dequeue()); // 输出: Charlie
System.out.println(queue.isEmpty()); // 输出: true
}
}Java中Queue接口
介绍Queue接口及其基本方法
在Java中，Queue接口定义了队列操作的行为。它扩展了Collection接口，并添加了一些队列特有的方法。以下是Queue接口的一些基本方法：
boolean add(E e): 向队列添加一个元素。如果不能添加，会抛出IllegalStateException。boolean offer(E e): 添加一个元素到队列，如果成功返回true，否则返回false。E remove(): 移除并返回队列头部的元素。如果不能移除，会抛出NoSuchElementException。E poll(): 移除并返回队列头部的元素，如果没有元素则返回null。E element(): 返回队列头部的元素但不移除它。如果不能获取，会抛出NoSuchElementException。E peek(): 返回队列头部的元素但不移除它，如果没有元素则返回null。
说明Queue与List和Set的不同之处
与List和Set不同，Queue提供了一种特定的集合顺序，即FIFO（先进先出）。List允许对序列进行随机访问，而Set不允许有重复的元素。相比之下，Queue更注重元素的添加和移除操作。
案例源码说明
下面是一个使用Java Queue接口的示例，我们将使用LinkedList作为队列的实现：
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// 向队列中添加元素
queue.add("First");
queue.add("Second");
queue.add("Third");
// 使用remove方法移除并获取队头元素
System.out.println(queue.remove()); // 输出: First
// 使用poll方法移除并获取队头元素，如果没有元素则返回null
System.out.println(queue.poll()); // 输出: Second
// 使用element方法获取队头元素但不移除
System.out.println(queue.element()); // 输出: Third
// 使用peek方法获取队头元素但不移除，如果为空则返回null
System.out.println(queue.peek()); // 输出: Third
// 再次使用remove方法移除剩余的元素
System.out.println(queue.remove()); // 输出: Third
System.out.println(queue.remove()); // 抛出: NoSuchElementException
}
}Queue的实现类
在Java中，Queue接口有多个实现类，每个实现类都有其特定的用途和性能特点。以下是几个常用的Queue实现类：
ArrayDeque
ArrayDeque是一个双端队列，可以作为一个队列或者栈使用。它允许元素从两端添加或移除。
LinkedList
LinkedList实现的Queue提供了高效的元素添加、移除操作，但可能不如ArrayDeque在队列操作中的性能表现。
PriorityQueue
PriorityQueue是一个不允许null元素的队列，它按照自然排序顺序或者根据提供的Comparator来决定元素的顺序。
比较各个实现类的用途和性能特点
ArrayDeque：适合需要从两端进行操作的场景，如滑动窗口问题。LinkedList：适合需要频繁插入和删除的场景，但可能在队列操作中不如ArrayDeque高效。PriorityQueue：适合需要根据优先级来访问元素的场景。
案例源码说明
使用ArrayDeque
代码语言：javascript复制import java.util.ArrayDeque;
public class ArrayDequeExample {
public static void main(String[] args) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
// 向队列两端添加元素
deque.addLast(1);
deque.addLast(2);
deque.addFirst(0);
// 从队列两端移除元素
System.out.println(deque.removeFirst()); // 输出: 0
System.out.println(deque.removeLast()); // 输出: 2
}
}使用LinkedList
代码语言：javascript复制import java.util.LinkedList;
import java.util.Queue;
public class LinkedListExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 向队列添加元素
queue.add(1);
queue.add(2);
// 使用poll和peek方法
System.out.println(queue.poll()); // 输出: 1
System.out.println(queue.peek()); // 输出: 2
}
}使用PriorityQueue
代码语言：javascript复制import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 向优先队列添加元素
priorityQueue.offer(10);
priorityQueue.offer(1);
priorityQueue.offer(5);
// 按优先级移除元素
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll()); // 输出: 1, 5, 10
}
}
}Queue的典型应用场景
在软件开发中，队列（Queue）是一种非常有用的数据结构，它在多种场景下都有应用。以下是一些典型的应用场景：
任务调度
队列常用于任务调度系统中，其中任务按照它们被添加的顺序执行。例如，一个打印队列可以确保打印任务按照提交的顺序进行。
消息队列
在分布式系统中，消息队列用于在不同服务或组件之间传递消息。消息队列可以作为缓冲区，平衡生产者和消费者之间的速率。
缓冲处理
队列还可以用于缓冲处理，例如在网络编程中，当处理速度跟不上数据到达速度时，可以使用队列临时存储数据。
案例源码说明
任务调度示例
代码语言：javascript复制import java.util.concurrent.LinkedBlockingQueue;
public class TaskScheduler {
private final LinkedBlockingQueue<Runnable> taskQueue = new LinkedBlockingQueue<>();
public void addTask(Runnable task) {
taskQueue.offer(() -> {
System.out.println("Executing task: " task);
task.run();
});
}
public void startScheduling() {
new Thread(() -> {
while (!Thread.currentThread().isInterrupted()) {
try {
taskQueue.take().run();
} catch (InterruptedException e) {
break;
}
}
}).start();
}
public static void main(String[] args) {
TaskScheduler scheduler = new TaskScheduler();
scheduler.addTask(() -> System.out.println("Task 1"));
scheduler.addTask(() -> System.out.println("Task 2"));
scheduler.startScheduling();
}
}在这个任务调度的示例中，我们创建了一个TaskScheduler，它使用LinkedBlockingQueue作为任务队列。每个任务被包装成一个新的Runnable，然后添加到队列中。调度器线程从队列中取出任务并执行它们。
消息队列示例
代码语言：javascript复制import java.util.concurrent.DelayQueue;
public class MessageQueue {
private final DelayQueue<ScheduledMessage> messageQueue = new DelayQueue<>();
public void sendMessage(ScheduledMessage message) {
messageQueue.put(message);
}
public void startMessageHandling() {
new Thread(() -> {
try {
while (!Thread.currentThread().isInterrupted()) {
ScheduledMessage message = messageQueue.take();
System.out.println("Handling message: " message.getMessage());
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
static class ScheduledMessage {
private final long scheduledTime;
private final String message;
public ScheduledMessage(long scheduledTime, String message) {
this.scheduledTime = scheduledTime;
this.message = message;
}
public long getScheduledTime() {
return scheduledTime;
}
public String getMessage() {
return message;
}
}
public static void main(String[] args) {
MessageQueue messageQueue = new MessageQueue();
messageQueue.sendMessage(new ScheduledMessage(System.currentTimeMillis() 5000, "Hello"));
messageQueue.sendMessage(new ScheduledMessage(System.currentTimeMillis() 10000, "World"));
messageQueue.startMessageHandling();
}
}在这个消息队列的示例中，我们使用了DelayQueue来存储带有一定延迟的消息。每个ScheduledMessage都有一个预定的时间戳，它将在那个时间戳之后变得可用。消息处理线程使用take方法从队列中取出并处理消息。
缓冲处理示例
代码语言：javascript复制import java.util.LinkedList;
import java.util.Queue;
public class BufferProcessor<T> {
private final Queue<T> buffer = new LinkedList<>();
private final int capacity;
public BufferProcessor(int capacity) {
this.capacity = capacity;
}
public void addElement(T element) {
synchronized (buffer) {
while (buffer.size() == capacity) {
try {
buffer.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return;
}
}
buffer.add(element);
buffer.notifyAll();
}
}
public T removeElement() {
synchronized (buffer) {
while (buffer.isEmpty()) {
try {
buffer.wait();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
return null;
}
}
buffer.notifyAll();
return buffer.remove();
}
}
}在这个缓冲处理的示例中，我们创建了一个BufferProcessor类，它使用LinkedList作为缓冲区。addElement方法用于向缓冲区添加元素，如果缓冲区已满，则等待。removeElement方法用于从缓冲区移除元素，如果缓冲区为空，则等待。这种同步机制确保了在生产者和消费者之间进行有效的缓冲。
