PriorityQueue
优先级队列，是0个或多个元素的集合，集合中的每个元素都有一个权重值，每次出队都弹出优先级最大或最小的元素。
主要属性
（1）默认容量是11；
（2）queue，元素存储在数组中，堆一般使用数组来存储；
（3）comparator，比较器，在优先级队列中，也有两种方式比较元素，一种是元素的自然顺序，一种是通过比较器来比较；
（4）modCount，修改次数，有这个属性表示PriorityQueue也是fast-fail的；
入队
（1）入队不允许null元素；
（2）如果数组不够用了，先扩容；
（3）如果还没有元素，就插入下标0的位置；
（4）如果有元素了，就插入到最后一个元素往后的一个位置（实际并没有插入哈）；
（5）自下而上堆化，一直往上跟父节点比较；
（6）如果比父节点小，就与父节点交换位置，直到出现比父节点大为止；
（7）由此可见，PriorityQueue是一个小顶堆。
扩容
（1）当数组比较小（小于64）的时候每次扩容容量翻倍；
（2）当数组比较大的时候每次扩容只增加一半的容量；
出队
（1）将队列首元素弹出；
（2）将队列末元素移到队列首；
（3）自上而下堆化，一直往下与最小的子节点比较；
（4）如果比最小的子节点大，就交换位置，再继续与最小的子节点比较；
（5）如果比最小的子节点小，就不用交换位置了，堆化结束；
（6）这就是堆中的删除堆顶元素；
结论
（1）PriorityQueue是一个小顶堆；
（2）PriorityQueue是非线程安全的；
（3）PriorityQueue不是有序的，只有堆顶存储着最小的元素；
（4）入队就是堆的插入元素的实现；
（5）出队就是堆的删除元素的实现；
ArrayBlockingQueue
ArrayBlockingQueue是java并发包下一个以数组实现的阻塞队列，它是线程安全的
主要属性
（1）利用数组存储元素；
（2）通过放指针和取指针来标记下一次操作的位置；
（3）利用重入锁来保证并发安全；
构造方法
（1）ArrayBlockingQueue初始化时必须传入容量，也就是数组的大小；
（2）可以通过构造方法控制重入锁的类型是公平锁还是非公平锁；
入队
（1）add(e)时如果队列满了则抛出异常；
（2）offer(e)时如果队列满了则返回false；
（3）put(e)时如果队列满了则使用notFull等待；
（4）offer(e, timeout, unit)时如果队列满了则等待一段时间后如果队列依然满就返回false；
（5）利用放指针循环使用数组来存储元素；
出队
（1）remove()时如果队列为空则抛出异常；
（2）poll()时如果队列为空则返回null；
（3）take()时如果队列为空则阻塞等待在条件notEmpty上；
（4）poll(timeout, unit)时如果队列为空则阻塞等待一段时间后如果还为空就返回null；
（5）利用取指针循环从数组中取元素；
总结
（1）ArrayBlockingQueue不需要扩容，因为是初始化时指定容量，并循环利用数组；
（2）ArrayBlockingQueue利用takeIndex和putIndex循环利用数组；
（3）入队和出队各定义了四组方法为满足不同的用途；
（4）利用重入锁和两个条件保证并发安全；
ArrayBlockingQueue有哪些缺点呢？
a）队列长度固定且必须在初始化时指定，所以使用之前一定要慎重考虑好容量；
b）如果消费速度跟不上入队速度，则会导致提供者线程一直阻塞，且越阻塞越多，非常危险；
c）只使用了一个锁来控制入队出队，效率较低，可以借助分段的思想把入队出队分裂成两个锁。
LinkedBlockingQueue
LinkedBlockingQueue是java并发包下一个以单链表实现的阻塞队列，它是线程安全的
主要属性
（1）capacity，有容量，可以理解为LinkedBlockingQueue是有界队列
（2）head, last，链表头、链表尾指针
（3）takeLock，notEmpty，take锁及其对应的条件
（4）putLock, notFull，put锁及其对应的条件
（5）入队、出队使用两个不同的锁控制，锁分离，提高效率
入队
（1）使用putLock加锁；
（2）如果队列满了就阻塞在notFull条件上；
（3）否则就入队；
（4）如果入队后元素数量小于容量，唤醒其它阻塞在notFull条件上的线程；
（5）释放锁；
（6）如果放元素之前队列长度为0，就唤醒notEmpty条件；
出队
（1）使用takeLock加锁；
（2）如果队列空了就阻塞在notEmpty条件上；
（3）否则就出队；
（4）如果出队前元素数量大于1，唤醒其它阻塞在notEmpty条件上的线程；
（5）释放锁；
（6）如果取元素之前队列长度等于容量，就唤醒notFull条件；
总结
（1）LinkedBlockingQueue采用单链表的形式实现；
（2）LinkedBlockingQueue采用两把锁的锁分离技术实现入队出队互不阻塞；
（3）LinkedBlockingQueue是有界队列，不传入容量时默认为最大int值；
LinkedBlockingQueue与ArrayBlockingQueue对比？
a）后者入队出队采用一把锁，导致入队出队相互阻塞，效率低下；
b）前才入队出队采用两把锁，入队出队互不干扰，效率较高；
c）二者都是有界队列，如果长度相等且出队速度跟不上入队速度，都会导致大量线程阻塞；
d）前者如果初始化不传入初始容量，则使用最大int值，如果出队速度跟不上入队速度，会导致队列特别长，占用大量内存；
SynchronousQueue
SynchronousQueue是java并发包下无缓冲阻塞队列，它用来在两个线程之间移交元素
主要属性
（1）这个阻塞队列里面是会自旋的；
（2）它使用了一个叫做transferer的东西来交换元素；
主要内部类
（1）定义了一个抽象类Transferer，里面定义了一个传输元素的方法；
（2）有两种传输元素的方法，一种是栈，一种是队列；
（3）栈的特点是后进先出，队列的特点是先进行出；
（4）栈只需要保存一个头节点就可以了，因为存取元素都是操作头节点；
（5）队列需要保存一个头节点一个尾节点，因为存元素操作尾节点，取元素操作头节点；
（6）每个节点中保存着存储的元素、等待着的线程，以及下一个节点；
构造方法
（1）默认使用非公平模式，也就是栈结构；
（2）公平模式使用队列，非公平模式使用栈；
入队
调用transferer的transfer()方法，传入元素e，说明是生产者
出队
调用transferer的transfer()方法，传入null，说明是消费者。
transferer
（1）如果栈中没有元素，或者栈顶元素跟将要入栈的元素模式一样，就入栈；
（2）入栈后自旋等待一会看有没有其它线程匹配到它，自旋完了还没匹配到元素就阻塞等待；
（3）阻塞等待被唤醒了说明其它线程匹配到了当前的元素，就返回匹配到的元素；
（4）如果两者模式不一样，且头节点没有在匹配中，就拿当前节点跟它匹配，匹配成功了就返回匹配到的元素；
（5）如果两者模式不一样，且头节点正在匹配中，当前线程就协助去匹配，匹配完成了再让当前节点重新入栈重新匹配；
总结
1）SynchronousQueue是java里的无缓冲队列，用于在两个线程之间直接移交元素；
（2）SynchronousQueue有两种实现方式，一种是公平（队列）方式，一种是非公平（栈）方式；
（3）栈方式中的节点有三种模式：生产者、消费者、正在匹配中；
（4）栈方式的大致思路是如果栈顶元素跟自己一样的模式就入栈并等待被匹配，否则就匹配，匹配到了就返回；
SynchronousQueue真的是无缓冲的队列吗？
通过源码分析，我们可以发现其实SynchronousQueue内部或者使用栈或者使用队列来存储包含线程和元素值的节点，如果同一个模式的节点过多的话，它们都会存储进来，且都会阻塞着，所以，严格上来说，SynchronousQueue并不能算是一个无缓冲队列。
SynchronousQueue有什么缺点呢？
试想一下，如果有多个生产者，但只有一个消费者，如果消费者处理不过来，是不是生产者都会阻塞起来？反之亦然。
这是一件很危险的事，所以，SynchronousQueue一般用于生产、消费的速度大致相当的情况，这样才不会导致系统中过多的线程处于阻塞状态。
PriorityBlockingQueue
PriorityBlockingQueue是java并发包下的优先级阻塞队列，它是线程安全的
主要属性
（1）依然是使用一个数组来使用元素；
（2）使用一个锁加一个notEmpty条件来保证并发安全；
（3）使用一个变量的CAS操作来控制扩容；
入队
入队的整个操作跟PriorityQueue几乎一致：
（1）加锁；
（2）判断是否需要扩容；
（3）添加元素并做自下而上的堆化；
（4）元素个数加1并唤醒notEmpty条件，唤醒取元素的线程；
（5）解锁；
扩容
（1）解锁，解除offer()方法中加的锁；
（2）使用allocationSpinLock变量的CAS操作来控制扩容的过程；
（3）旧容量小于64则翻倍，旧容量大于64则增加一半；
（4）创建新数组；
（5）修改allocationSpinLock为0，相当于解锁；
（6）其它线程在扩容的过程中要让出CPU；
（7）再次加锁；
（8）新数组创建成功，把旧数组元素拷贝过来，并返回到offer()方法中继续添加元素操作；
出队
（1）加锁；
（2）判断是否出队成功，未成功就阻塞在notEmpty条件上；
（3）出队时弹出堆顶元素，并把堆尾元素拿到堆顶；
（4）再做自上而下的堆化；
（5）解锁；
总结
（1）PriorityBlockingQueue整个入队出队的过程与PriorityQueue基本是保持一致的；
（2）PriorityBlockingQueue使用一个锁+一个notEmpty条件控制并发安全；
（3）PriorityBlockingQueue扩容时使用一个单独变量的CAS操作来控制只有一个线程进行扩容；
（4）入队使用自下而上的堆化；
（5）出队使用自上而下的堆化；
为什么PriorityBlockingQueue不需要notFull条件？
因为PriorityBlockingQueue在入队的时候如果没有空间了是会自动扩容的，也就不存在队列满了的状态，也就是不需要等待通知队列不满了可以放元素了，所以也就不需要notFull条件了。
LinkedTransferQueue
LinkedTransferQueue是LinkedBlockingQueue、SynchronousQueue（公平模式）、ConcurrentLinkedQueue三者的集合体，它综合了这三者的方法，并且提供了更加高效的实现方式。
继承体系
LinkedTransferQueue实现了TransferQueue接口，而TransferQueue接口是继承自BlockingQueue的，所以LinkedTransferQueue也是一个阻塞队列。
存储结构
LinkedTransferQueue使用了一个叫做dual data structure的数据结构，或者叫做dual queue，译为双重数据结构或者双重队列。
双重队列是什么意思呢？
放取元素使用同一个队列，队列中的节点具有两种模式，一种是数据节点，一种是非数据节点。
放元素时先跟队列头节点对比，如果头节点是非数据节点，就让他们匹配，如果头节点是数据节点，就生成一个数据节点放在队列尾端（入队）。
取元素时也是先跟队列头节点对比，如果头节点是数据节点，就让他们匹配，如果头节点是非数据节点，就生成一个非数据节点放在队列尾端（入队）。 不管是放元素还是取元素，都先跟头节点对比，如果二者模式不一样就匹配它们，如果二者模式一样，就入队。
典型的单链表结构，内部除了存储元素的值和下一个节点的指针外，还包含了是否为数据节点和持有元素的线程。是无界的一个阻塞队列。
总结
（1）LinkedTransferQueue可以看作LinkedBlockingQueue、SynchronousQueue（公平模式）、ConcurrentLinkedQueue三者的集合体；
（2）LinkedTransferQueue的实现方式是使用一种叫做双重队列的数据结构；
（3）不管是取元素还是放元素都会入队；
（4）先尝试跟头节点比较，如果二者模式不一样，就匹配它们，组成CP，然后返回对方的值；
（5）如果二者模式一样，就入队，并自旋或阻塞等待被唤醒；
（6）至于是否入队及阻塞有四种模式，NOW、ASYNC、SYNC、TIMED；
（7）LinkedTransferQueue全程都没有使用synchronized、重入锁等比较重的锁，基本是通过 自旋+CAS 实现；
（8）对于入队之后，先自旋一定次数后再调用LockSupport.park()或LockSupport.parkNanos阻塞；
- LinkedTransferQueue与SynchronousQueue（公平模式）有什么异同呢？
（1）在java8中两者的实现方式基本一致，都是使用的双重队列；
（2）前者完全实现了后者，但比后者更灵活；
（3）后者不管放元素还是取元素，如果没有可匹配的元素，所在的线程都会阻塞；
（4）前者可以自己控制放元素是否需要阻塞线程，比如使用四个添加元素的方法就不会阻塞线程，只入队元素，使用transfer()会阻塞线程；
（5）取元素两者基本一样，都会阻塞等待有新的元素进入被匹配到；
ConcurrentLinkedQueue
ConcurrentLinkedQueue只实现了Queue接口，并没有实现BlockingQueue接口，所以它不是阻塞队列，也不能用于线程池中，但是它是线程安全的，可用于多线程环境中。
主要属性
就这两个主要属性，一个头节点，一个尾节点。这是一个无界的单链表实现的队列。
入队
入队整个流程还是比较清晰的，这里有个前提是出队时会把出队的那个节点的next设置为节点本身。
（1）定位到链表尾部，尝试把新节点到后面；
（2）如果尾部变化了，则重新获取尾部，再重试；
出队
（1）定位到头节点，尝试更新其值为null；
（2）如果成功了，就成功出队；
（3）如果失败或者头节点变化了，就重新寻找头节点，并重试；
（4）整个出队过程没有一点阻塞相关的代码，所以出队的时候不会阻塞线程，没找到元素就返回null；
总结
（1）ConcurrentLinkedQueue不是阻塞队列；
（2）ConcurrentLinkedQueue不能用在线程池中；
（3）ConcurrentLinkedQueue使用（CAS+自旋）更新头尾节点控制出队入队操作；
- ConcurrentLinkedQueue与LinkedBlockingQueue对比？
（1）两者都是线程安全的队列；
（2）两者都可以实现取元素时队列为空直接返回null，后者的poll()方法可以实现此功能；
（3）前者全程无锁，后者全部都是使用重入锁控制的；
（4）前者效率较高，后者效率较低；
（5）前者无法实现如果队列为空等待元素到来的操作；
（6）前者是非阻塞队列，后者是阻塞队列；
（7）前者无法用在线程池中，后者可以；
DelayQueue
DelayQueue是java并发包下的延时阻塞队列，常用于实现定时任务。
从继承体系可以看到，DelayQueue实现了BlockingQueue，所以它是一个阻塞队列。
另外，DelayQueue还组合了一个叫做Delayed的接口，DelayQueue中存储的所有元素必须实现Delayed接口。
Delayed是一个继承自Comparable的接口，并且定义了一个getDelay()方法，用于表示还有多少时间到期，到期了应返回小于等于0的数值。
主要属性
从属性我们可以知道，延时队列主要使用优先级队列来实现，并辅以重入锁和条件来控制并发安全。
因为优先级队列是无界的，所以这里只需要一个条件就可以了。
入队
（1）加锁；
（2）添加元素到优先级队列中；
（3）如果添加的元素是堆顶元素，就把leader置为空，并唤醒等待在条件available上的线程；
（4）解锁；
出队
（1）加锁；
（2）检查第一个元素，如果为空或者还没到期，就返回null；
（3）如果第一个元素到期了就调用poll()弹出第一个元素；
（4）解锁。
总结
（1）DelayQueue是阻塞队列；
（2）DelayQueue内部存储结构使用优先级队列；
（3）DelayQueue使用重入锁和条件来控制并发安全；
（4）DelayQueue常用于定时任务；
- java中的线程池实现定时任务是直接用的DelayQueue吗？
当然不是，ScheduledThreadPoolExecutor中使用的是它自己定义的内部类DelayedWorkQueue，其实里面的实现逻辑基本都是一样的，只不过DelayedWorkQueue里面没有使用现在的PriorityQueue，而是使用数组又实现了一遍优先级队列，本质上没有什么区别。
ArrayDeque
双端队列是一种特殊的队列，它的两端都可以进出元素，故而得名双端队列。
ArrayDeque是一种以数组方式实现的双端队列，它是非线程安全的。
通过继承体系可以看，ArrayDeque实现了Deque接口，Deque接口继承自Queue接口，它是对Queue的一种增强。
从属性我们可以看到，ArrayDeque使用数组存储元素，并使用头尾指针标识队列的头和尾，其最小容量是8。
通过构造方法，我们知道默认初始容量是16，最小容量是8。
入队
（1）入队有两种方式，从队列头或者从队列尾；
（2）如果容量不够了，直接扩大为两倍；
（3）通过取模的方式让头尾指针在数组范围内循环；
（4）x & (len - 1) = x % len，使用&的方式更快；
出队
（1）出队有两种方式，从队列头或者从队列尾；
（2）通过取模的方式让头尾指针在数组范围内循环；
（3）出队之后没有缩容哈哈^^
总结
（1）ArrayDeque是采用数组方式实现的双端队列；
（2）ArrayDeque的出队入队是通过头尾指针循环利用数组实现的；
（3）ArrayDeque容量不足时是会扩容的，每次扩容容量增加一倍；
（4）ArrayDeque可以直接作为栈使用；
LinkedList
（1）LinkedList是一个以双链表实现的List；
（2）LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；
（3）LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；
（4）LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；
（5）LinkedList不支持随机访问，所以访问非队列首尾的元素比较低效；
（6）LinkedList在功能上等于ArrayList + ArrayDeque；