【常用的队列总结】

队列的介绍

Queue队列的基本概念与操作

在 Java 中，队列（Queue）是一种常见的数据结构，它按照先进先出（FIFO）的原则管理元素。队列通常用于在数据集合中添加元素，并按照它们被添加的顺序移除元素。Java 提供了丰富的队列实现，可以满足不同场景下的需求。

队列的基本概念

队列是一种线性数据结构，它有两个基本操作：入队（enqueue）和出队（dequeue）。入队将元素添加到队列的末尾，而出队则从队列的头部获取并移除元素。因此，队列的特点是先进先出，即最先入队的元素最先出队。

常见的队列介绍

非阻塞队列

LinkedList:

LinkedList 是 Java 中实现了 List 接口的类，它基于双向链表数据结构实现了列表的操作。除了实现了 List 接口之外，LinkedList 还实现了 Queue 接口，因此也可以用作队列。
LinkedList的特点：
1.双向链表结构：每个节点都包含指向前一个节点和后一个节点的引用，这使得在任意位置插入或删除元素的操作都是高效的。
2.非线程安全：LinkedList 不是线程安全的，如果需要在多线程环境中使用，需要通过额外的同步手段来保证线程安全性。
常用的方法：

添加元素：
add(E e): 将指定元素添加到列表末尾。
add(int index, E element): 在指定位置插入元素。
获取元素：
get(int index): 返回列表中指定位置的元素。
getFirst(): 返回列表中的第一个元素。
getLast(): 返回列表中的最后一个元素。
删除元素：
remove(): 移除并返回列表中的第一个元素。
remove(int index): 移除列表中指定位置的元素。
removeFirst(): 移除并返回列表中的第一个元素。
removeLast(): 移除并返回列表中的最后一个元素。
队列操作：
offer(E e): 将指定元素添加到队列的尾部。
poll(): 移除并返回队列的头部元素。
peek(): 返回队列的头部元素，但不移除。
判断元素是否存在：
contains(Object element)：检查链表是否包含指定元素。
获取链表大小和清空链表：
size()：获取链表中元素的个数。
isEmpty()：检查链表是否为空。
clear()：清空链表中的所有元素。
栈操作（LIFO）：
push(E e): 将元素压入栈（等同于 addFirst(E e)）。
pop(): 移除并返回栈顶元素（等同于 removeFirst()）。

ArrayDeque:

ArrayDeque 是 Java 中实现了 Deque 接口的类，是一个基于数组的双端队列。它在两端进行插入和删除操作都非常高效，是实现栈和队列操作的理想选择。ArrayDeque 可以用作栈、队列或双端队列。
ArrayDeque的特点：
1.双端队列：可以在队列的两端进行添加和删除操作。
2.基于数组：内部使用数组来存储元素，初始容量可以动态调整。
3.无界队列：可以根据需要自动扩容，因此不限制大小。
4.线程不安全：不是线程安全的，在多线程环境中使用时需要外部同步。
5.高效：相比 LinkedList，ArrayDeque 的性能更高，因为它没有节点的额外开销。
常用方法：

添加元素：
addFirst(E e): 在队列头部添加元素。
addLast(E e): 在队列尾部添加元素。
offerFirst(E e): 在队列头部添加元素，返回 true 如果添加成功。
offerLast(E e): 在队列尾部添加元素，返回 true 如果添加成功。
获取元素：
getFirst(): 获取队列头部的元素。
getLast(): 获取队列尾部的元素。
peekFirst(): 获取但不移除队列头部的元素，返回 null 如果队列为空。
peekLast(): 获取但不移除队列尾部的元素，返回 null 如果队列为空。
删除元素：
removeFirst(): 移除并返回队列头部的元素。
removeLast(): 移除并返回队列尾部的元素。
pollFirst(): 移除并返回队列头部的元素，返回 null 如果队列为空。
pollLast(): 移除并返回队列尾部的元素，返回 null 如果队列为空。
栈操作（LIFO）：
push(E e): 将元素压入栈（等同于 addFirst(E e)）。
pop(): 移除并返回栈顶元素（等同于 removeFirst()）。

PriorityQueue:

PriorityQueue 是 Java 中提供的一个基于优先级堆实现的队列，它可以确保每次出队（移除）操作总是返回队列中优先级最高的元素。它在需要频繁访问和删除优先级最高的元素的场景下非常有用。

PriorityQueue的特点：
1.基于堆：PriorityQueue 使用二叉堆（通常是最小堆）实现，能够提供对最小（或最大）元素的高效访问和删除。
2.自然顺序或自定义顺序：可以按照元素的自然顺序（实现 Comparable 接口）或通过指定的 Comparator 进行排序。
3.无界队列：默认情况下是无界的，但其内部容量会根据需要自动扩展。
4.线程不安全：不是线程安全的，如果在多线程环境中使用，需要额外的同步。
5.元素排序：插入元素后不会保持队列的顺序，但在访问时总是返回优先级最高的元素。
常用方法：

添加元素：
add(E e): 将指定元素插入优先级队列，若插入失败抛出异常。
offer(E e): 将指定元素插入优先级队列，返回 true 如果插入成功。
获取元素：
peek(): 返回队列头部的元素（优先级最高的元素），但不移除，如果队列为空返回 null。
删除元素：
poll(): 移除并返回队列头部的元素（优先级最高的元素），如果队列为空返回 null。
remove(Object o): 从队列中移除指定元素。
其他操作：
size(): 返回队列中的元素数量。
isEmpty(): 检查队列是否为空。

阻塞队列

ArrayBlockingQueue

ArrayBlockingQueue 是 Java 中的一种阻塞队列实现，它基于数组并具有固定容量。它在队列满或队列空时会使得相应的插入或移除操作阻塞，是在生产者-消费者场景中常用的一个类。
特点：
1.固定容量：ArrayBlockingQueue 在创建时必须指定容量。
2.线程安全：内部使用锁和条件变量来控制并发访问，确保线程安全。
3.FIFO顺序：元素按先进先出（FIFO）的顺序进行插入和删除。
常用方法：

添加元素
add(E e): 将指定元素插入队列，如果队列已满，则抛出 IllegalStateException。
offer(E e): 将指定元素插入队列，如果队列已满，则返回 false。
put(E e): 将指定元素插入队列，如果队列已满，则阻塞直到有可用空间。
获取元素
peek(): 获取队列头部的元素，但不移除，如果队列为空，则返回 null。
poll(): 获取并移除队列头部的元素，如果队列为空，则返回 null。
take(): 获取并移除队列头部的元素，如果队列为空，则阻塞直到有可用元素。
其他操作
size(): 返回队列中的元素数量。
isEmpty(): 检查队列是否为空。
remainingCapacity(): 返回队列剩余的可用容量。

LinkedBlockingQueue

LinkedBlockingQueue 是 Java 中的一种阻塞队列实现，它基于链接节点（链表）并且可以选择有界或无界。它在多线程环境下非常适合用来实现生产者-消费者模型，因为它支持阻塞的插入和移除操作。
特点：
1.有界或无界：可以在初始化时指定容量，未指定时默认最大容量为 Integer.MAX_VALUE。
2.线程安全：使用独立的锁来控制插入和删除操作，确保线程安全。
3.FIFO顺序：元素按先进先出（FIFO）的顺序进行插入和删除。
4.高吞吐量：由于插入和删除操作使用了独立的锁，可以在多线程环境中提供较高的吞吐量。
常用方法：

添加元素
add(E e): 将指定元素插入队列，如果队列已满，则抛出 IllegalStateException。
offer(E e): 将指定元素插入队列，如果队列已满，则返回 false。
put(E e): 将指定元素插入队列，如果队列已满，则阻塞直到有可用空间。
offer(E e, long timeout, TimeUnit unit): 将指定元素插入队列，在指定时间内等待可用空间，如果队列已满且超时，则返回 false。
获取元素
peek(): 获取队列头部的元素，但不移除，如果队列为空，则返回 null。
poll(): 获取并移除队列头部的元素，如果队列为空，则返回 null。
take(): 获取并移除队列头部的元素，如果队列为空，则阻塞直到有可用元素。
poll(long timeout, TimeUnit unit): 获取并移除队列头部的元素，在指定时间内等待，如果队列为空且超时，则返回 null。
其他操作
size(): 返回队列中的元素数量。
isEmpty(): 检查队列是否为空。
remainingCapacity(): 返回队列剩余的可用容量。

PriorityBlockingQueue

PriorityBlockingQueue 是 Java 中的一种阻塞队列实现，它基于优先级堆实现，元素按自然顺序或指定的比较器顺序进行排序。与普通的阻塞队列不同，PriorityBlockingQueue 中的元素不是按照插入顺序进行处理，而是按照优先级顺序进行处理。这使得它非常适合需要处理优先级任务的场景。
特点：
1.无界队列：PriorityBlockingQueue 是一个无界队列，其容量为 Integer.MAX_VALUE。
2.线程安全：内部使用并发控制机制，确保多线程环境下的安全性。
3.元素排序：元素按自然顺序（通过 Comparable 接口）或指定的比较器进行排序。
4.阻塞操作：在获取元素时会阻塞直到有可用元素。
常用方法：

添加元素
add(E e): 将指定元素插入队列。
offer(E e): 将指定元素插入队列。
put(E e): 将指定元素插入队列（由于队列无界，此方法实际上不会阻塞）。
offer(E e, long timeout, TimeUnit unit): 将指定元素插入队列，等待指定时间（由于队列无界，此方法实际上不会阻塞）。
获取元素
peek(): 获取队列头部的元素，但不移除，如果队列为空，则返回 null。
poll(): 获取并移除队列头部的元素，如果队列为空，则返回 null。
take(): 获取并移除队列头部的元素，如果队列为空，则阻塞直到有可用元素。
poll(long timeout, TimeUnit unit): 获取并移除队列头部的元素，等待指定时间，如果队列为空且超时，则返回 null。
其他操作
size(): 返回队列中的元素数量。
isEmpty(): 检查队列是否为空。

DelayQueue

DelayQueue 是 Java 中的一种阻塞队列实现，它适用于在一段时间之后才能获取元素的场景。队列中的元素必须实现 Delayed 接口，并在指定的延迟期满之后才能从队列中获取到。这使得 DelayQueue 特别适用于实现任务调度和超时任务处理等功能。
特点：
1.无界队列：DelayQueue 是一个无界队列，其容量为 Integer.MAX_VALUE。
2.线程安全：内部使用并发控制机制，确保多线程环境下的安全性。
3.基于时间的排序：元素根据剩余的延迟时间进行排序，延迟时间最短的元素优先处理。
4.元素必须实现 Delayed 接口：队列中的元素需要实现 getDelay(TimeUnit unit) 和 compareTo(Delayed o) 方法。
常用方法：

添加元素
add(E e): 将指定元素插入队列。
offer(E e): 将指定元素插入队列。
put(E e): 将指定元素插入队列（由于队列无界，此方法实际上不会阻塞）。
offer(E e, long timeout, TimeUnit unit): 将指定元素插入队列，等待指定时间（由于队列无界，此方法实际上不会阻塞）。
获取元素
peek(): 获取队列头部的元素，但不移除，如果队列为空或头部元素的延迟时间未到，则返回 null。
poll(): 获取并移除队列头部的元素，如果队列为空或头部元素的延迟时间未到，则返回 null。
take(): 获取并移除队列头部的元素，如果队列为空或头部元素的延迟时间未到，则阻塞直到有可用元素。
poll(long timeout, TimeUnit unit): 获取并移除队列头部的元素，等待指定时间，如果队列为空或头部元素的延迟时间未到且超时，则返回 null。
其他操作
size(): 返回队列中的元素数量。
isEmpty(): 检查队列是否为空。

SynchronousQueue

SynchronousQueue 是 Java 中的一种特殊的阻塞队列实现，它没有内部容量或者缓冲区，每一个 put 操作必须等待一个对应的 take 操作，反之亦然。这意味着在 SynchronousQueue 中，元素只能在生产者和消费者线程之间直接传递。
特点：
1.无容量：SynchronousQueue 没有容量，无法缓存元素。
2.线程安全：内部使用并发控制机制，确保多线程环境下的安全性。
3.直接传递：每个插入操作必须等待一个移除操作，反之亦然。
4.适用于移交：特别适用于需要在线程之间移交任务的场景。
常用方法：

添加元素
put(E e): 将指定元素插入队列，如果没有相应的取出操作，则阻塞。
offer(E e): 将指定元素插入队列，如果没有相应的取出操作，则返回 false。
offer(E e, long timeout, TimeUnit unit): 将指定元素插入队列，等待指定时间，如果没有相应的取出操作，则返回 false。
获取元素
take(): 获取并移除队列中的元素，如果没有相应的插入操作，则阻塞。
poll(): 获取并移除队列中的元素，如果没有相应的插入操作，则返回 null。
poll(long timeout, TimeUnit unit): 获取并移除队列中的元素，等待指定时间，如果没有相应的插入操作，则返回 null。
其他操作
size(): 始终返回 0，因为 SynchronousQueue 不存储任何元素。