BlockingQueue及其实现

<h1>1. 前言</h1>
BlockingQueue即阻塞队列，它是基于ReentrantLock，依据它的基本原理，我们可以实现Web中的长连接聊天功能，当然其最常用的还是用于实现生产者与消费者模式，大致如下图所示：
<img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-ed0b3ec3ee8287f3d744d0ede6662411.png">
 
<blockquote>
在Java中，BlockingQueue是一个接口，它的实现类有ArrayBlockingQueue、DelayQueue、 LinkedBlockingDeque、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等，它们的区别主要体现在存储结构上或对元素操作上的不同，但是对于take与put操作的原理，却是类似的。
</blockquote>
<h1>2. 阻塞与非阻塞</h1>
<h2>入队</h2>
<blockquote>
offer(E e)：如果队列没满，立即返回true；如果队列满了，立即返回false-->不阻塞
put(E e)：如果队列满了，一直阻塞，直到队列不满了或者线程被中断-->阻塞
offer(E e, long timeout, TimeUnit unit)：在队尾插入一个元素,，如果队列已满，则进入等待，直到出现以下三种情况：-->阻塞
被唤醒
等待时间超时
当前线程被中断
</blockquote>
<h2>出队</h2>
<blockquote>
poll()：如果没有元素，直接返回null；如果有元素，出队
take()：如果队列空了，一直阻塞，直到队列不为空或者线程被中断-->阻塞
poll(long timeout, TimeUnit unit)：如果队列不空，出队；如果队列已空且已经超时，返回null；如果队列已空且时间未超时，则进入等待，直到出现以下三种情况：
被唤醒
等待时间超时
当前线程被中断
</blockquote>
 
<h1>3. LinkedBlockingQueue 源码分析</h1>
LinkedBlockingQueue是一个基于链表实现的可选容量的阻塞队列。队头的元素是插入时间最长的，队尾的元素是最新插入的。新的元素将会被插入到队列的尾部。 
LinkedBlockingQueue的容量限制是可选的，如果在初始化时没有指定容量，那么默认使用int的最大值作为队列容量。
<h2>底层数据结构</h2>
LinkedBlockingQueue内部是使用链表实现一个队列的，但是却有别于一般的队列，在于该队列至少有一个节点，头节点不含有元素。结构图如下：
<img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-d41a83eaf2cdb387c0dc23432065ac0a.png">
 
 
<h2>原理</h2>
LinkedBlockingQueue中维持两把锁，一把锁用于入队，一把锁用于出队，这也就意味着，同一时刻，只能有一个线程执行入队，其余执行入队的线程将会被阻塞；同时，可以有另一个线程执行出队，其余执行出队的线程将会被阻塞。换句话说，虽然入队和出队两个操作同时均只能有一个线程操作，但是可以一个入队线程和一个出队线程共同执行，也就意味着可能同时有两个线程在操作队列，那么为了维持线程安全，LinkedBlockingQueue使用一个AtomicInterger类型的变量表示当前队列中含有的元素个数，所以可以确保两个线程之间操作底层队列是线程安全的。
<h2>源码分析</h2>
LinkedBlockingQueue可以指定容量，内部维持一个队列，所以有一个头节点head和一个尾节点last，内部维持两把锁，一个用于入队，一个用于出队，还有锁关联的Condition对象。主要对象的定义如下：
<blockquote>
//容量，如果没有指定，该值为Integer.MAX_VALUE;
private final int capacity;
//当前队列中的元素
private final AtomicInteger count =new AtomicInteger();
//队列头节点，始终满足head.item==null
transient Node head;
//队列的尾节点，始终满足last.next==null
private transient Node last;
//用于出队的锁
private final ReentrantLock takeLock =new ReentrantLock();
//当队列为空时，保存执行出队的线程
private final Condition notEmpty = takeLock.newCondition();
//用于入队的锁
private final ReentrantLock putLock =new ReentrantLock();
//当队列满时，保存执行入队的线程
private final Condition notFull = putLock.newCondition();
</blockquote>
<h3>put(E e)方法</h3>
put(E e)方法用于将一个元素插入到队列的尾部，其实现如下：
<blockquote>
public void put(E e)throws InterruptedException {
//不允许元素为null
 if (e ==null)
throw new NullPointerExceptio

BlockingQueue及其实现

浏览过的版块