Queue 队列

1.队列特性

1.可以把 LinkedList当Queue来使用 ==> Deque 双端队列 可查看 Java 容器类 一、List 列表 篇
2.通常不允许 null
3.FIFO 先进先出 – Queue默认
LIFO 后进先出（堆栈）
优先级队列 按优先级出

2.基本操作

3.分类

双端队列, 单端队列

ConcurrentLinkedQueue 并发队列

1）基于链接节点、无界、线程安全队列、FIFO（先进先出）

2）不允许使用 null 元素

采用“无等待 (wait-free)”算法 CAS

该算法基于 Maged M. Michael 和 Michael L. Scott 合著的 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 中描述的算法

注意：与大多数 collection 不同，size 方法不是 一个固定时间操作, 由于这些队列的异步特性，确定当前元素的数量需要遍历这些元素

内存一致性效果：
当存在其他并发 collection 时将对象放入 ConcurrentLinkedQueue 之前的线程中的操作 happen-before 随后通过另一线程从 ConcurrentLinkedQueue 访问或移除该元素的操作

private transient volatile Node<E> head; // 首节点 volatile
private transient volatile Node<E> tail; // 尾节点 volatile
static final class Node<E> {
    volatile Node<E> prev;
    volatile E item;
    volatile Node<E> next;

    Node() {
        // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR
    }
// head节点存放链表第一个item为null的节点
// tail则并不是总指向最后一个节点
// item用来存放节点的值
// next用来存放下一个节点，
// ==> 从而链接为一个单向无界列表

3）开源框架中使用：Tomcat中NioEndPoint中的每个poller里面就维护一个ConcurrentLinkedQueue用来作为**缓冲存放任务**

4）使用CAS非阻塞算法实现使用CAS解决了当前节点与next节点之间的安全链接和对当前节点值的赋值

[size()]

• 由于使用 CAS 没有使用锁，所以获取size的时候有可能进行 offer，poll 或者 remove 操作，
  导致获取的元素个数不精确，所以在并发情况下size函数不是很有用
  另外第一次 peek 或者 first 时候会把 head 指向第一个真正的队列元素

• 线程安全的，volatile + CAS 可知入队出队 函数都是操作 volatile 变量：head，tail。
  所以要保证队列线程安全只需要保证对这两个 Node 操作的可见性和原子性，由于 volatile 本身保证可见性，所以只需要看下多线程下如果保证对着两个变量操作的原子性。

• 对于 offer 操作是在 tail 后面添加元素，也就是调用 tail.casNext 方法，
  而这个方法是使用的CAS操作，只有一个线程会成功，然后失败的线程会循环一下，重新获取tail，
  然后执行 casNext 方法。

• 对于 poll 也是这样的。

ConcurrentLinkedDeque 并发双向队列

非阻塞，无锁，无界 ，线程安全双端操作的队列

• 双向链表结构的无界并发队列

• 使用CAS实现并发安全

• 同时支持 FIFO 和 FILO

• 适合“多生产，多消费”的场景

• 内存一致性遵循对 ConcurrentLinkedDeque 的插入操作

• 先行发生于(happen-before) 访问或移除 操作。

BlockingQueue (7种阻塞队列)

• 这个后续会逐一相熟每种队列特殊性 2020年12月10日

• ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列

• LinkedBlockingQueue ：一个由链表结构组成的可选有界阻塞队列
  如果未指定容量，那么容量将等于 Integer.MAX_VALUE

• LinkedBlockingDeque：一个由链表结构组成的可选范围双向阻塞队列
  如果未指定容量，那么容量将等于 Integer.MAX_VALUE

• PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列

• DelayQueue：一个使用优先级队列实现的无界阻塞队列, 只有在延迟期满时才能从中提取元素

• SynchronousQueue：一个不存储元素、没有内部容量的阻塞队列

• LinkedTransferQueue：一个由链表结构组成的无界阻塞TransferQueue队列

1）支持两个附加操作的 Queue，这两个操作是：

​ 元素时等待队列变为非空
​ 元素时等待空间变得可用(阻塞)

2）BlockingQueue 方法以四种形式出现，

​ 对于不能立即满足但可能在将来某一时刻可以满足的操作，
​ 这四种形式的处理方式不同：

1）抛出一个异常
2）返回一个特殊值（null 或 false，具体取决于操作）
3）在操作可以成功前，无限期地阻塞当前线程
4）在放弃前只在给定的最大时间限制内阻塞

3）不接受 null 元素

试图 add、put 或 offer 一个 null 元素时，某些实现会抛出 NullPointerException。null 被用作指示 poll 操作失败的警戒值

4）可以是限定容量的

它在任意给定时间都可以有一个 remainingCapacity，超出此容量，便无法无阻塞地 put 附加元素,
没有任何内部容量约束的 BlockingQueue 总是报告 Integer.MAX_VALUE 的剩余容量

5）实现主要用于生产者-使用者队列

BlockingQueue 可以安全地与多个生产者和多个使用者一起使用, 但它另外还支持 Collection 接口。
因此，举例来说，使用 remove(x) 从队列中移除任意一个元素是有可能的。
然而，这种操作通常不 会有效执行，只能有计划地偶尔使用，比如在取消排队信息时。

6）实现是线程安全的

所有排队方法都可以使用内部锁或其他形式的并发控制来自动达到它们的目的。
然而，大量的 Collection 操作（addAll、containsAll、retainAll 和 removeAll）没有 必要自动执行，除非在实现中特别说明。
因此，举例来说，在只添加了 c 中的一些元素后，addAll(c) 有可能失败（抛出一个异常）

7）BlockingQueue 实质上不 支持使用任何一种 “close” 或 “shutdown” 操作来指示不再添加任何项。

这种功能的需求和使用有依赖于实现的倾向。
例如，一种常用的策略是：对于生产者，插入特殊的 end-of-stream 或 poison 对象，并根据使用者获取这些对象的时间来对它们进行解释。

8）内存一致性效果：当存在其他并发 collection 时，将对象放入 BlockingQueue 之前的线程中的操作，
happen-before 随后通过另一线程从 BlockingQueue中访问或移除该元素的操作。

参考：

• Blog
• Java 容器类
• Java 容器类 一、List 列表