Queue

Queue接口

Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

Deque接口

Deque extends Queue

**双向队列(Deque)**，是Queue的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll)，如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。

Queue和 Deque 共有方法

boolean add(E e)：在队列尾部添加一个元素 成功返回true 失败抛出异常

boolean offer(E e)：在队列尾部添加一个元素 成功返回true，失败返回false

E remove()：取出队列的第一个元素，并从队列中移除该元素，成功返回该元素，失败返回false，如果指定元素为空，抛出NullPointerException

E poll()：取出队列第一个元素，并从队列中移除该元素，成功返回该元素，失败返回null

E element()：取出队列第一个元素，不移除，成功返回该元素，失败抛出异常

E peek()：取出队列第一个元素，不移除,成功返回该元素，失败返回null

Deque的独有方法

void addFirst(E e)：在队列头部 添加一个元素，失败抛出异常

void addLast(E e)：在队列尾部 添加一个元素，失败抛出异常

boolean offerFirst(E e)：在队列头部 添加一个元素，成功返回true ，失败返回false

boolean offerLast(E e)：在队列尾部 添加一个元素，成功返回true ，失败返回false

E removeFirst()：取出队列的第一个元素，并移除该元素，成功返回该元素，失败抛出异常

E removeLast()：取出队列的最后一个元素，并移除该元素，成功返回该元素，失败抛出异常

E pollFirst()：取出队列的第一个元素，并移除该元素，成功返回该元素，失败返回null

E pollLast()：取出队列的最后一个元素，并移除该元素，成功返回该元素，失败返回null

E getFirst()：取出队列的第一个元素，不移除，成功返回该元素，失败抛出异常

E getLast()：取出队列的最后一个元素，不移除，成功返回该元素，失败抛出异常

E peekFirst()：取出队列的第一个元素，不移除，成功返回该元素，失败返回null

E peekLast()：取出队列的最后一个元素，不移除，成功返回该元素，失败返回null

boolean removeFirstOccurrence(Object o)：移除双向队列中第一个出现的该元素，成功返回true，失败抛出异常

boolean removeLastOccurrence(Object o)：移除双向队列中最后一个出现的该元素，成功返回true，失败抛出异常

ArrayDeque

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

• ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
• ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
• ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
• ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，**ArrayDeque 也可以用于实现栈。**

ArrayDeque和LinktedList对比

内存访问效率：ArrayDeque 内部使用数组来存储元素，而 LinkedList 使用链表结构。数组具有连续的内存布局，可以利用 CPU 缓存的局部性原理，提供更好的内存访问局部性。相比之下，链表中的元素在内存中是分散存储的，访问时需要跳跃指针，导致缓存未命中的可能性增加，降低了访问效率。

随机访问效率：由于 ArrayDeque 使用数组作为底层数据结构，支持高效的随机访问。可以通过索引直接访问数组中的元素，时间复杂度为 O(1)。而 LinkedList 需要从头或尾开始遍历链表，以找到指定位置的元素，时间复杂度为 O(n)。在需要频繁随机访问队列中的元素时，ArrayDeque 的效率更高。

空间效率：由于 ArrayDeque 使用数组存储元素，不需要为每个元素额外存储指针信息，相比之下，LinkedList 需要为每个元素存储指向前后节点的指针。因此，ArrayDeque 的内存占用通常比 LinkedList 更低。

迭代器性能：ArrayDeque 的迭代器在底层数组上直接进行迭代，效率较高。而 LinkedList 的迭代器需要在链表节点之间进行指针跳转，性能相对较低。

PriorityQueue

优先队列，底层实现是一个堆。在使用堆实现的优先队列中，每次插入一个元素时，都会根据其优先级找到合适的位置进行插入，保持堆的性质。当需要取出元素时，总是取出堆顶（即优先级最高）的元素，并重新调整堆的结构以满足堆的性质。

• PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
• PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
• PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第 K 大的数、带权图的遍历等，所以需要会熟练使用才行。

优先队列的常见操作包括：

insert(key)：向优先队列中插入一个元素，时间复杂度为O(logN)。

deleteMin()：删除并返回优先队列中优先级最高的元素，时间复杂度为O(logN)。

getMin()：返回优先队列中优先级最高的元素，但不进行删除，时间复杂度为O(1)。

isEmpty()：检查优先队列是否为空，时间复杂度为O(1)。

size()：返回优先队列中元素的个数，时间复杂度为O(1)。

add(元素)或offer(元素)：向队列中添加元素。

remove()或poll()：移除并返回队列中的第一个（最高优先级）元素。

peek()：返回队列中的第一个（最高优先级）元素，但不进行移除。

默认情况下，优先队列中的元素按照自然顺序进行排序，即小顶堆。但也可以通过传递一个自定义的Comparator对象来指定元素的比较规则。

创建小顶堆

PriorityQueue<Integer> pq = new PriorityQueue<>();
Collections.addAll(pq,3,4,1,6,7);
System.out.println(pq); //[1, 4, 3, 6, 7]

创建大顶堆

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
  @Override
  public int compare(Integer o1, Integer o2) {
    return o2 - o1;
  }
});

Collections.addAll(pq,3,4,1,6,7);
System.out.println(pq); //[7, 6, 1, 3, 4]

BlockingQueue接口

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

public interface BlockingQueue<E> extends Queue<E> {
  // ...
}

BlockingQueue 常用于生产者-消费者模型中，生产者线程会向队列中添加数据，而消费者线程会从队列中取出数据进行处理。

Java 中常用的阻塞队列实现类有以下几种：

1. ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
2. LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是， 它仅支持非公平的锁访问机制。
3. PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。
4. SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。
5. DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。
6. ……

日常开发中，这些队列使用的其实都不多，了解即可。

ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？

ArrayBlockingQueue 和 LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。不过，不过它们之间也存在下面这些区别：

• 底层实现：ArrayBlockingQueue 基于数组实现，而 LinkedBlockingQueue 基于链表实现。
• 是否有界：ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。LinkedBlockingQueue 创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。
• 锁是否分离： ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；LinkedBlockingQueue中的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。
• 内存占用：ArrayBlockingQueue 需要提前分配数组内存，而 LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间。