Queue详解
基本概念
- Java 中的
Queue接口表示一种先进先出（FIFO, First In First Out）的数据结构，但实际上它也支持其他插入和删除策略。 Queue是 Java 集合框架的一部分，它继承自Collection接口，并且定义了许多用于队列操作的方法。
功能分类
-
双端队列：继承
Deque接口的队列，支持从两端插入和移除元素。ArrayDeque和LinkedList都是Deque的实现类，可以用来创建栈或双端队列。 -
阻塞队列：继承
BlockingQueue或BlockingDeque接口的队列，当队列满或空时，插入或移除操作将会阻塞的队列。阻塞队列都是线程安全的。例如，ArrayBlockingQueue和LinkedBlockingQueue等。 -
并发队列：在多线程环境中，使用普通的队列实现可能会导致数据不一致或竞争问题。Java 提供了线程安全的并发队列，
ConcurrentLinkedQueue、ConcurrentLinkedDeque和BlockingQueue。 -
有界队列：如
ArrayBlockingQueue可以设置一个最大容量，当队列达到这个容量时，将不再接受新的元素插入，除非有其他元素被移除。 -
无界队列：一些队列实现没有固定的容量限制，如
LinkedList和ArrayDeque。 -
优先队列：
PriorityQueue或PriorityBlockingQueue，根据元素的自然顺序或通过提供的Comparator来确定元素插入位置，队列内元素有序排列。当从队列中移除元素时，总是返回具有最高优先级的元素。 -
延迟队列：
DelayQueue继承子BlockingQueue，它允许元素在被添加时指定一个延迟时间。只有当这个延迟时间过去之后，元素才会变得可见。延迟队列中元素是按照延迟时间排序的，因此内部元素需要实现Delayed接口，其中compareTo方法，用于队列元素排序。延迟队列通常用于实现定时任务或事件调度等功能。 -
同步队列：
SynchronousQueue继承自BlockingQueue，用于在线程之间直接传递元素。它没有内部缓冲区，也就是说它不能存储任何元素。因此，当一个线程试图向SynchronousQueue插入一个元素时（例如使用put方法），它会一直阻塞，直到另一个线程从队列中取出这个元素（例如使用take方法）。常用于生产者消费者模式。
主要方法
普通队列
| 操作 | 抛出异常 | 返回特殊值 |
|---|---|---|
| 插入 | add(e) | offer(e) |
| 删除 | remove() | poll() |
| 检查 | element() | peek() |
当队列为空或容量已满时，remove、element和add方法会抛出异常，而poll、peek和offer方法则会返回false或null。
双端队列
| 操作 | 方法 |
|---|---|
| 尾部插入（队列） | offer(e) |
| 头部删除（队列） | poll() |
| 尾部插入（栈） | push(e) |
| 尾部删除（栈） | pop() |
既支持队列相关操作，也支持栈相关操作
阻塞队列
| 操作 | 方法 |
|---|---|
| 插入 | put(e) |
| 删除 | take() |
阻塞队列中的put和take方法有阻塞特性，而offer和poll方法无阻塞特性，是非阻塞方法
使用示例
以下是一个使用 SynchronousQueue 的生产者消费者模式示例：
package leetcode.editor.cn;
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.TimeUnit;
public class SynchronousQueueExample {
public static void main(String[] args) throws InterruptedException {
/**
* 创建一个非公平模式的 SynchronousQueue
* 若队列中没有元素，当两个线程同时请求，优先插入操作
* 若队列中已有元素，当两个线程同时请求，优先删除操作
*/
SynchronousQueue<Integer> queue = new SynchronousQueue<>(false);
Thread producerThread = new Thread(() -> {
try {
for (int i = 1; i <= 5; i++) {
System.out.println("Producer putting " + i);
queue.put(i);
TimeUnit.MILLISECONDS.sleep(100);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
});
Thread consumerThread = new Thread(() -> {
try {
for (int i = 1; i <= 5; i++) {
Integer value = queue.take();
System.out.println("Consumer taking " + value);
TimeUnit.MILLISECONDS.sleep(100);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
});
producerThread.start();
consumerThread.start();
producerThread.join();
consumerThread.join();
}
}
总结
实际常用的是LinkedList和ArrayDeque，既可以作为队列使用，也可以作为栈使用