阻塞队列
 
大厂面试题：
 
我们都知道ArrayList是线程不安全的，请编码写一个不安全的案例并给出解决方案？
 
公平锁/非公平锁/可重入锁/递归锁/自旋锁谈谈你的理解？请手写一个自旋锁。
 
CountDownLatch、CyclicBarrier、Semaphore使用过吗？
 
阻塞队列知道吗？
 
线程池用过吗？ThreadPoolExecutor谈谈你的理解？
 
线程池用过吗？生产上你是如何设置合理参数？
 
死锁编码及定位分析？
 
1、阻塞队列是什么？
 
阻塞队列首先是一个队列，当队列是空的时候，从队列获取元素的操作将会被阻塞，当队列是满的时候，从队列插入元素的操作将会被阻塞。
 
 
       消息中间件底层用的就是阻塞队列。
 
2、阻塞队列好处
 
       在多线程领域，所谓阻塞，在某些情况下会挂起线程（即阻塞），一旦条件满足，被挂起的线程又会自动被唤醒。
 
       为什么需要使用BlockingQueue？
 
       好处是我们不需要关心什么时候去阻塞线程，什么时候需要唤醒线程，因为这一切BlockingQue都给你一手包办了。
 
       在Concurrent包发布以前，在多线程环境下，我们每个程序员都要去控制这些细节，尤其还要兼顾效率与线程安全，这会给我们的程序带来不小的复杂度。
 
3、阻塞队列BlockingQueue接口架构图
 
、
 
4、阻塞队列BlockingQueue种类
 
（1）ArrayBlockingQueue：由数组结构组成的有界阻塞队列。
 
（2）LinkedBlockingQueue：由链表结果组成的有界阻塞队列（默认大小Integer.MAX_VALUE）阻塞队列。
 
（3）SychronousQueue：不存储元素的阻塞队列，也即单个元素队列。
 
（4）PriorityBlockingQueue：支持优先级排序的无界阻塞队列。
 
（5）DelayQueue：使用优先级队列实现的延迟无界阻塞队列。
 
（6）LinkedTransferQueue：由链表结构组成的无界阻塞队列。
 
（7）LinkedBlockingDeque：由链表结构组成的双端阻塞队列。
 
5、阻塞队列BlockingQueue核心方法
 
 
（1）抛出异常的方法
 
       当阻塞队列满时，再往队列里add元素会抛出IllegalStateException：Queue full；
 
       当阻塞队列空时，再从队列里remove移除元素会抛NoSuchElementException。
 
（2）返回特殊值（boolean值）的方法
 
       插入成功，返回true；插入失败，返回false；
 
       删除成功返回出队列元素；删除失败返回null；
 
（3）阻塞的方法
 
       当阻塞队列满时，生产者线程继续往队列里put元素，队列会一直阻塞生产线程直到put数据or响应中断退出。
 
       当阻塞队列空时，消费者线程试图take队列里的元素，队列会一直阻塞消费者线程直到队列有可用元素。、
 
（4）超时的方法
 
       当向阻塞队列offer元素时候，时间超过了设定的值，就会出现超时中断；
 
       当向阻塞队列poll元素时候，时间超过了设定的值，就会出现超时中断。
 
5、阻塞队列BlockingQueue核心方法代码验证
 
（1）抛出异常的方法代码验证
 
       Demo One：add方法抛出异常
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里add元素会抛出IllegalStateException:Queue full.
 
 * 当阻塞队列空时，再往队列里remove元素会抛出NoSuchElementException.
 
 */
 
public class BlockingQueueDemoOne {
 
    public static void main(String[] args) {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        System.out.println(blockingQueue.add("吴用"));
 
        System.out.println(blockingQueue.add("宋江"));
 
        System.out.println(blockingQueue.add("李逵"));
 
        System.out.println(blockingQueue.add("卢俊义"));
 
        System.out.println(blockingQueue.add("高俅"));
 
 
 
        // 再往阻塞队列添加一个元素就会抛出I了legalStateException:Queue full.
 
        System.out.println(blockingQueue.add("武松"));
 
 
 
    }
 
}
 
程序执行结果如下：
 
 
       Demo Two：remove方法抛出异常
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
/**
 
 * 当阻塞队列满时，再往队列里add元素会抛出IllegalStateException:Queue full.
 
 * 当阻塞队列空时，再往队列里remove元素会抛出NoSuchElementException.
 
 */
 
public class BlockingQueueDemoOne {
 
    public static void main(String[] args) {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 阻塞队列add方法抛出异常演示
 
        System.out.println(blockingQueue.add("吴用"));
 
        System.out.println(blockingQueue.add("宋江"));
 
        System.out.println(blockingQueue.add("李逵"));
 
        System.out.println(blockingQueue.add("卢俊义"));
 
        System.out.println(blockingQueue.add("高俅"));
 
 
 
        // 再往阻塞队列添加一个元素就会抛出I了legalStateException:Queue full.
 
//        System.out.println(blockingQueue.add("武松"));
 
 
 
        // 阻塞队列remove方法抛出异常演示
 
        System.out.println(blockingQueue.remove());
 
        System.out.println(blockingQueue.remove());
 
        System.out.println(blockingQueue.remove());
 
        System.out.println(blockingQueue.remove());
 
        System.out.println(blockingQueue.remove());
 
 
 
        // 再往阻塞队列里remove一个元素就会抛出NoSuchElementException
 
        System.out.println(blockingQueue.remove());
 
 
 
    }
 
}
 
程序执行结果如下：
 
 
       Demo Three:element检查方法
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里add元素会抛出IllegalStateException:Queue full.
 
 * 当阻塞队列空时，再往队列里remove元素会抛出NoSuchElementException.
 
 */
 
public class BlockingQueueDemoOne {
 
    public static void main(String[] args) {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 阻塞队列add方法抛出异常演示
 
        System.out.println(blockingQueue.add("吴用"));
 
        System.out.println(blockingQueue.add("宋江"));
 
        System.out.println(blockingQueue.add("李逵"));
 
        System.out.println(blockingQueue.add("卢俊义"));
 
        System.out.println(blockingQueue.add("高俅"));
 
 
 
        // 检查队列队首元素是啥？或者检查队列是否为空。
 
        System.err.println(blockingQueue.element());
 
 
 
    }
 
}
 
程序执行结果如下：
 
 
（2）返回特殊值的方法（boolean值返回）
 
Demo One：阻塞队列offer方法的使用
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里offer元素会返回false.
 
 * 当阻塞队列空时，再往队列里poll元素会返回null.
 
 */
 
public class BlockingQueueDemoTwo {
 
    public static void main(String[] args) {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，offer方法返回false演示
 
        System.out.println(blockingQueue.add("吴用"));
 
        System.out.println(blockingQueue.add("宋江"));
 
        System.out.println(blockingQueue.add("李逵"));
 
        System.out.println(blockingQueue.add("卢俊义"));
 
        System.out.println(blockingQueue.add("高俅"));
 
 
 
        // 此时再往阻塞队列offer一个元素就会返回false
 
        System.out.println(blockingQueue.offer("武松"));
 
    }
 
}
 
程序执行结果如下：
 
 
       Demo Two：阻塞队列poll方法的使用
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里offer元素会返回false.
 
 * 当阻塞队列空时，再往队列里poll元素会返回null.
 
 */
 
public class BlockingQueueDemoTwo {
 
    public static void main(String[] args) {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，offer方法返回false演示
 
        System.out.println(blockingQueue.add("吴用"));
 
        System.out.println(blockingQueue.add("宋江"));
 
        System.out.println(blockingQueue.add("李逵"));
 
        System.out.println(blockingQueue.add("卢俊义"));
 
        System.out.println(blockingQueue.add("高俅"));
 
 
 
        // 此时再往阻塞队列offer一个元素就会返回false
 
        System.out.println(blockingQueue.offer("武松"));
 
 
 
        // 当阻塞队列为空时，poll方法返回null演示
 
        System.out.println(blockingQueue.poll());
 
        System.out.println(blockingQueue.poll());
 
        System.out.println(blockingQueue.poll());
 
        System.out.println(blockingQueue.poll());
 
        System.out.println(blockingQueue.poll());
 
 
 
        // 此时再往阻塞队列执行poll一个元素就会返回null
 
        System.out.println(blockingQueue.poll());
 
 
 
    }
 
}
 
程序执行结果如下：
 
 
       Demo Three：
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里offer元素会返回false.
 
 * 当阻塞队列空时，再往队列里poll元素会返回null.
 
 */
 
public class BlockingQueueDemoTwo {
 
    public static void main(String[] args) {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，offer方法返回false演示
 
        System.out.println(blockingQueue.add("吴用"));
 
        System.out.println(blockingQueue.add("宋江"));
 
        System.out.println(blockingQueue.add("李逵"));
 
        System.out.println(blockingQueue.add("卢俊义"));
 
        System.out.println(blockingQueue.add("高俅"));
 
 
 
        // peek方法返回阻塞队列队首元素，如果此阻塞队列为空，则返回为null
 
        System.out.println(blockingQueue.peek());
 
 
 
    }
 
}
 
（3）阻塞队列的方法
 
       Demo One：阻塞队列put方法使用
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里put元素会阻塞队列.
 
 * 当阻塞队列空时，再往队列里take元素会阻塞队列.
 
 */
 
public class BlockingQueueDemoThree {
 
    public static void main(String[] args) throws InterruptedException {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，put方法会阻塞队列演示
 
        blockingQueue.put("吴用");
 
        blockingQueue.put("宋江");
 
        blockingQueue.put("李逵");
 
        blockingQueue.put("卢俊义");
 
        blockingQueue.put("高俅");
 
 
 
        //此时再往阻塞队列put一个元素时，会阻塞队列
 
        blockingQueue.put("武松");
 
 
 
    }
 
}
 
程序执行结果如下：
 
 
       Demo Two：阻塞队列take方法使用
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里put元素会阻塞队列.
 
 * 当阻塞队列空时，再往队列里take元素会阻塞队列.
 
 */
 
public class BlockingQueueDemoThree {
 
    public static void main(String[] args) throws InterruptedException {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，put方法会阻塞队列演示
 
        blockingQueue.put("吴用");
 
        blockingQueue.put("宋江");
 
        blockingQueue.put("李逵");
 
        blockingQueue.put("卢俊义");
 
        blockingQueue.put("高俅");
 
 
 
        //此时再往阻塞队列put一个元素时，会阻塞队列
 
//        blockingQueue.put("武松");
 
 
 
        // 当阻塞队列空时，take方法会阻塞队列演示
 
        blockingQueue.take();
 
        blockingQueue.take();
 
        blockingQueue.take();
 
        blockingQueue.take();
 
        blockingQueue.take();
 
 
 
        // 此时再往阻塞队列take一个元素时，会阻塞队列
 
        blockingQueue.take();
 
    }
 
}
 
程序执行结果如下：
 
 
（4）超时中断的方法
 
       Demo One：阻塞队列offer超时中断演示
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
import java.util.concurrent.TimeUnit;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里offer元素阻塞队列会超时中断.
 
 * 当阻塞队列空时，再往队列里poll元素阻塞队列会超时中断.
 
 */
 
public class BlockingQueueDemoFour {
 
    public static void main(String[] args) throws InterruptedException {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，offer方法执行超过3秒，阻塞队列会超时中断演示
 
        System.out.println(blockingQueue.offer("吴用", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("宋江", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("李逵", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("卢俊义", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("高俅", 3, TimeUnit.SECONDS));
 
 
 
        //此时再往阻塞队列offer一个元素时，阻塞队列3秒后会超时中断
 
        System.out.println(blockingQueue.offer("武松", 3, TimeUnit.SECONDS));
 
    }
 
}
 
程序执行结果如下：当往阻塞队列添加第六个元素的时候，队列添加不进去，3秒后会超时中断。
 
 
       Demo Two：阻塞队列poll超时中断演示
 
package com.wwl.juc;
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 
import java.util.concurrent.BlockingQueue;
 
import java.util.concurrent.TimeUnit;
 
 
 
/**
 
 * 当阻塞队列满时，再往队列里offer元素阻塞队列会超时中断.
 
 * 当阻塞队列空时，再往队列里poll元素阻塞队列会超时中断.
 
 */
 
public class BlockingQueueDemoFour {
 
    public static void main(String[] args) throws InterruptedException {
 
        BlockingQueue blockingQueue = new ArrayBlockingQueue(5);
 
        // 当阻塞队列满时，offer方法执行超过3秒，阻塞队列会超时中断演示
 
        System.out.println(blockingQueue.offer("吴用", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("宋江", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("李逵", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("卢俊义", 3, TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.offer("高俅", 3, TimeUnit.SECONDS));
 
 
 
        //此时再往阻塞队列offer一个元素时，阻塞队列3秒后会超时中断
 
        System.out.println(blockingQueue.offer("武松", 3, TimeUnit.SECONDS));
 
 
 
        // 当阻塞队列空时，poll方法执行超过3秒，阻塞队列会超时中断演示
 
        System.out.println(blockingQueue.poll(3,TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.poll(3,TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.poll(3,TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.poll(3,TimeUnit.SECONDS));
 
        System.out.println(blockingQueue.poll(3,TimeUnit.SECONDS));
 
 
 
        // 此时再往阻塞队列poll一个元素时，超过3秒，阻塞队列会超时中断
 
        System.out.println(blockingQueue.poll(3,TimeUnit.SECONDS));
 
    }
 
}
 
程序执行结果如下：
 
 
 

在并发编程中，有时候需要使用线程安全的队列。如果要实现一个线程安全的队列有两种方式：一种是使用阻塞算法，另一种是使用非阻塞算法。
 
使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。非阻塞的实现方式则可以使用自旋+CAS的方式来实现。
 
基本概念
 
阻塞队列与非阻塞队列
 
阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作支持阻塞的插入和移除方法。
 
 
支持阻塞的插入方法offer：当队列满时，队列会阻塞插入元素的线程，直到队列不满。
 
 
支持阻塞的移除方法take：在队列为空时，获取元素的线程会等待队列变为非空。
 
 
阻塞队列常用于生产者和消费者的场景，生产者是向队列里添加元素的线程，消费者是从队列里取元素的线程。阻塞队列就是生产者用来存放元素、消费者用来获取元素的容器。
 
非阻塞队列：若队列为空从中获取元素则会返回空，若队列满了插入元素则会抛出异常。
 
有界队列与无界队列
 
 
有界队列：就是有固定大小的队列。比如设定了固定大小的ArrayBlockingQueue，又或者大小为0，只是在生产者和消费者中做中转用的SynchronousQueue。
 
 
无界队列：指的是没有设置固定大小的队列。这些队列的特点是可以直接入列，直到溢出。当然现实几乎不会有到这么大的容量（超过 Integer.MAX_VALUE），所以从使用者的体验上，就相当于 “无界”。
 
 
Java中的阻塞队列
 
 
 
ArrayBlockingQueue：一个由数组结构组成的有界阻塞队列。
 
 
LinkedBlockingQueue：一个由链表结构组成的有界阻塞队列。
 
 
PriorityBlockingQueue：一个支持优先级排序的无界阻塞队列。
 
 
DelayQueue：一个使用优先级队列实现的延迟无界阻塞队列。
 
 
SynchronousQueue：一个不存储元素的阻塞队列。
 
 
LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
 
 
LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。
 
 
另外还有一个DelayedWorkQueue，是ScheduledThreadPoolExecutor的内部类。
 
阻塞队列中的方法
 
方法类型
抛出异常
特殊值
阻塞
超时
插入时队列满了的表现
add（IllegalStateException）
offer（false）
put
offer
移除时队列为空的表现
remove（NoSuchElementException）
poll（null）
take
poll
检查时队列为空的表现
element（NoSuchElementException）
peek（null）
不可用
不可用
ArrayBlockingQueue
 
基于数组实现的有界阻塞队列，ArrayBlockingQueue内部维护这一个定长数组，阻塞队列的大小在初始化时就已经确定了，其后无法更改。
 
ArrayBlockingQueue支持公平性和非公平性，默认采用非公平模式，可以通过构造函数设置为公平访问策略。
 
PriorityBlockingQueue
 
PriorityBlockingQueue是支持优先级的无界队列。默认情况下采用自然顺序排序，当然也可以通过自定义Comparator来指定元素的排序顺序，不能保证同优先级元素的顺序。
 
PriorityBlockingQueue内部采用二叉堆的实现方式。
 
DelayQueue
 
DelayQueue是一个支持延时操作的无界阻塞队列。列头的元素是最先“到期”的元素，如果队列里面没有元素到期，是不能从列头获取元素的，哪怕有元素也不行。也就是说只有在延迟期满时才能够从队列中去元素。
 
它主要运用于如下场景：
 
 
缓存系统的设计：缓存是有一定的时效性的，可以用DelayQueue保存缓存的有效期，然后利用一个线程查询DelayQueue，如果取到元素就证明该缓存已经失效了。
 
 
定时任务的调度：DelayQueue保存当天将要执行的任务和执行时间，一旦取到元素（任务），就执行该任务。
 
 
DelayQueue采用支持优先级的PriorityQueue来实现，但是队列中的元素必须要实现Delayed接口，Delayed接口用来标记那些应该在给定延迟时间之后执行的对象，该接口提供了getDelay()方法返回元素节点的剩余时间。同时，元素也必须要实现compareTo()方法，compareTo()方法需要提供与getDelay()方法一致的排序。
 
SynchronousQueue
 
SynchronousQueue是一个神奇的队列，他是一个不存储元素的阻塞队列，也就是说他的每一个put操作都需要等待一个take操作，否则就不能继续添加元素了，有点儿像Exchanger，类似于生产者和消费者进行交换。
 
队列本身不存储任何元素，所以非常适用于传递性场景，两者直接进行对接。其吞吐量会高于ArrayBlockingQueue和LinkedBlockingQueue。
 
SynchronousQueue支持公平和非公平的访问策略，在默认情况下采用非公平性，也可以通过构造函数来设置为公平性。
 
SynchronousQueue的实现核心为Transferer接口，该接口有TransferQueue和TransferStack两个实现类，分别对应着公平策略和非公平策略。接口Transferer有一个tranfer()方法，该方法定义了转移数据，如果e != null，相当于将一个数据交给消费者，如果e == null，则相当于从一个生产者接收一个消费者交出的数据。
 
LinkedTransferQueue
 
LinkedTransferQueue与其他BlockingQueue相比，他多实现了一个接口TransferQueue，该接口是对BlockingQueue的一种补充，多了tryTranfer()和transfer()两类方法：
 
 
tranfer()：若当前存在一个正在等待获取的消费者线程，即立刻移交之。 否则，会插入当前元素e到队列尾部，并且等待进入阻塞状态，到有消费者线程取走该元素。
 
 
tryTranfer()： 若当前存在一个正在等待获取的消费者线程（使用take()或者poll()函数），使用该方法会即刻转移/传输对象元素e；若不存在，则返回false，并且不进入队列。这是一个不阻塞的操作。
 
 
LinkedBlockingDeque
 
LinkedBlockingDeque是一个有链表组成的双向阻塞队列，与前面的阻塞队列相比它支持从两端插入和移出元素。以first结尾的表示从对头操作，以last结尾的表示从对尾操作。
 
在初始化LinkedBlockingDeque时可以初始化队列的容量，用来防止其再扩容时过渡膨胀。另外双向阻塞队列可以运用在“工作窃取”模式中。
 
ArrayBlockingQueue的源码分析
 
ArrayBlockingQueue，一个由数组实现的有界阻塞队列。该队列采用FIFO的原则对元素进行排序添加的。
 
数据结构
 
public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    final Object[] items; // 存储元素的数组

    int takeIndex; // 队首位置

    int putIndex; // 队尾位置

    int count; // 元素的个数

    final ReentrantLock lock; // 锁，出列入列都必须获取该锁，两个步骤共用一个锁

    private final Condition notEmpty; // 出队条件

    private final Condition notFull; // 入队条件
 
ArrayBlockingQueue内部使用可重入锁ReentrantLock + Condition来完成多线程环境的并发操作。
 
构造方法
 
// 指定初始化时元素个数，可见是个有界队列
public ArrayBlockingQueue(int capacity) {
    this(capacity, false);
}

// 指定初始化时元素个数和公平策略
public ArrayBlockingQueue(int capacity, boolean fair) {
    if (capacity <= 0)
        throw new IllegalArgumentException();
    this.items = new Object[capacity];
    lock = new ReentrantLock(fair);
    notEmpty = lock.newCondition();
    notFull =  lock.newCondition();
}

// 指定初始化时元素个数和公平策略，指定初始化集合中的元素
public ArrayBlockingQueue(int capacity, boolean fair,
                          Collection<? extends E> c) {
    this(capacity, fair);

    final ReentrantLock lock = this.lock;
    lock.lock(); // Lock only for visibility, not mutual exclusion
    try {
        int i = 0;
        try {
            for (E e : c) {
                checkNotNull(e);
                items[i++] = e;
            }
        } catch (ArrayIndexOutOfBoundsException ex) {
            throw new IllegalArgumentException();
        }
        count = i;
        putIndex = (i == capacity) ? 0 : i;
    } finally {
        lock.unlock();
    }
}
 
offer()
 
public boolean offer(E e) {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        if (count == items.length)
            // 队满了
            return false;
        else {
            enqueue(e);
            return true;
        }
    } finally {
        lock.unlock();
    }
}

// 插入队尾
private void enqueue(E x) {
    final Object[] items = this.items;
    items[putIndex] = x;
    if (++putIndex == items.length)
        putIndex = 0;
    count++;
    notEmpty.signal();
}
 
put()
 
public void put(E e) throws InterruptedException {
    checkNotNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await(); // 堆满等待
        enqueue(e); // 插入队尾
    } finally {
        lock.unlock();
    }
}
 
take()
 
public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == 0)
            notEmpty.await(); // 队空等待
        return dequeue(); // 出队
    } finally {
        lock.unlock();
    }
}

private E dequeue() {
    final Object[] items = this.items;
    @SuppressWarnings("unchecked")
    E x = (E) items[takeIndex];
    items[takeIndex] = null;
    if (++takeIndex == items.length)
        takeIndex = 0;
    count--;
    if (itrs != null)
        itrs.elementDequeued();
    notFull.signal();
    return x;
}
 
poll()
 
public E poll() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 队空返回null，不等待
        return (count == 0) ? null : dequeue();
    } finally {
        lock.unlock();
    }
}
 
手写阻塞队列
 
package com.morris.concurrent.pattern.guardedsuspension;

import java.util.ArrayList;

public class ArrayListBlockingQueue<T> {

    private ArrayList<T> taskList;

    private int queueSize;

    public ArrayListBlockingQueue(int queueSize) {
        this.queueSize = queueSize;
        this.taskList = new ArrayList<>(queueSize);
    }

    public void offer(T t) throws InterruptedException {
        synchronized (this.taskList) {
            while(this.taskList.size() == queueSize) {
                this.taskList.wait();
            }
            this.taskList.add(t);
            this.taskList.notifyAll();
        }
    }

    public T take() throws InterruptedException {
        synchronized (this.taskList) {
            while (this.taskList.isEmpty()) {
                this.taskList.wait();
            }
            this.taskList.notifyAll();
            return this.taskList.remove(0);
        }
    }
}

    在多线程领域，所谓的阻塞，在某些情况下会挂起线程即阻塞，一旦满足某条件时，被挂起的线程又会自动被唤醒。队列的数据结构大家并不陌生，先进先出，先到先得，什么是阻塞队列呢，顾名思义，首先它是一个队列，当阻塞队列是空时，从队列中获取元素的操作将会被阻塞，当阻塞队列是满时，往队列里添加元素的操作将会被阻塞，那为什么需要阻塞队列呢，好处就是我们不需要关心什么时候需要阻塞线程，什么时候需要唤醒线程，，在concurrent包发布之前，线程的控制，需要程序员自己来通过synchronized来控制线程的阻塞（wait）和唤醒（notify，notifyAll），当concurrent包发布之后这一切阻塞线程都为我们一手包办了，那阻塞队列有哪些种类呢。
 
ArrayBlockingQueue 是一个基于数组的有界阻塞队列，次队列按FIFO（先进先出）原则对元素进行排序
LinkedBlockingQueue 是一个基于链表结构的有界（默认值是Integer.MAX_VALUE）阻塞队列，次队列按FIFO（先进先出）排序元素，吞吐量通常要高于ArrayBlockQueue
SynchronousQuere是一个不存储元素的阻塞队列，每个插入操作必须等到另一个线程调用移除操作，否则插入操作一直处于阻塞状态，吞吐量通常要高于前两种
PriorityBlockingQueue 支持优先级排序的无界阻塞队列
DelayQueue 使用优先级队列实现的延迟无界阻塞队列
LinkedTransferQueue 有链表结构组成的无界阻塞队列
LinkedBlockingDeque 有链表结构组成的双向阻塞队列
     以后的文章我们着重讲解ArrayBlockingQueue，LinkedBlockingQueue和SynchronousQuere，因为后边说到线程池的时候主要是这三个。
 
    接下来，我们按照下边的表来一个一个介绍阻塞线程的方法类型。
 
方法类型
抛出异常
特殊值
阻塞
超时
插入
add
offer
put
offer
移除
remove
poll
take
poll
检查
 
element
 
peek
不可用
不可用
    先来看，抛出异常的add，remove，和element的阻塞队列的例子
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.BlockingQueue;
 
 
public class BlockingQueueDemo {
 
 
    public static void main(String[] args) throws Exception {
 
 
        BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<String>(3);
         System.err.println(blockingQueue.add("a"));
         System.err.println(blockingQueue.add("b"));
         System.err.println(blockingQueue.add("c"));
         //        System.err.println(blockingQueue.add("d"));
 
 
        System.err.println(blockingQueue.element());
 
 
        System.err.println(blockingQueue.remove());
         System.err.println(blockingQueue.remove());
         System.err.println(blockingQueue.remove());
         //        System.err.println(blockingQueue.remove());
 
 
    }
 
 
}
 
 
当add方法的注释放开的时候，会抛出下边的错误。
 
 
 
true
 true
 true
 Exception in thread "main" java.lang.IllegalStateException: Queue full
     at java.base/java.util.AbstractQueue.add(AbstractQueue.java:98)
     at java.base/java.util.concurrent.ArrayBlockingQueue.add(ArrayBlockingQueue.java:326)
     at BlockingQueueDemo.main(BlockingQueueDemo.java:12)
  
 
 
当remove方法的注释放开的时候，会抛出下边的错误，说明add方法，remove方法一言不和就抛出异常。
 
 
 
true
 true
 true
 a
 a
 b
 c
 Exception in thread "main" java.util.NoSuchElementException
     at java.base/java.util.AbstractQueue.remove(AbstractQueue.java:117)
     at BlockingQueueDemo.main(BlockingQueueDemo.java:19)
  
 
 
    再来看，不抛出异常的offer，peek，和poll的阻塞队列的例子
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.BlockingQueue;
 
 
public class BlockingQueueDemo {
 
 
    public static void main(String[] args) throws Exception {
 
 
        BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<String>(3);
         System.err.println(blockingQueue.offer("a"));
         System.err.println(blockingQueue.offer("b"));
         System.err.println(blockingQueue.offer("c"));
         System.err.println(blockingQueue.offer("d"));
 
 
        System.err.println(blockingQueue.peek());
 
 
        System.err.println(blockingQueue.poll());
         System.err.println(blockingQueue.poll());
         System.err.println(blockingQueue.poll());
         System.err.println(blockingQueue.poll());
 
 
    }
 
 
}
 
 
    从下边的执行结果来看，当往阻塞队列里追加元素的时候会返回false，以及当从空的阻塞队列中删除元素的时候，会返回null，这样程序相比直接抛出异常会显得友好些。
 
 
 
true
 true
 true
 false
 a
 a
 b
 c
 null
 
 
    我们再来说说上表中第三种情况的put，take方法，阻塞，即不抛异常，也不返回结果，我们在看来看一个demo
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.BlockingQueue;
 
 
public class BlockingQueueDemo {
 
 
    public static void main(String[] args) throws Exception {
 
 
        BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<String>(3);
         blockingQueue.put("a");
         blockingQueue.put("b");
         blockingQueue.put("c");
         System.err.println("===============");
         //blockingQueue.put("d");
 
 
        blockingQueue.take();
         blockingQueue.take();
         blockingQueue.take();
         //blockingQueue.take();
     }
 
 
}
 
 
    首先创建容量为3的阻塞队列，当3个元素加满的时候，在想往容器中追加元素的时候，阻塞队列会一直等待，take方法也是一样的，当阻塞队列为空的时候，在想从队列当中take元素时，也是会阻塞。
 
    最后，我们看看第四种情况，带时间参数的阻塞队列。
 
 
 
import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.BlockingQueue;
 import java.util.concurrent.TimeUnit;
 
 
public class BlockingQueueDemo {
 
 
    public static void main(String[] args) throws Exception {
 
 
        BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<String>(3);
         System.err.println(blockingQueue.offer("a", 2, TimeUnit.SECONDS));
         System.err.println(blockingQueue.offer("b", 2, TimeUnit.SECONDS));
         System.err.println(blockingQueue.offer("c", 2, TimeUnit.SECONDS));
         System.err.println(blockingQueue.offer("d", 2, TimeUnit.SECONDS));
 
 
    }
 
 
}
 
 
    从执行结果来看，设定阻塞时间后，在指定的时间内没有添加成功的话，会返回结果，不阻塞，相比阻塞的方法也得友好。
 
 
 
true
 true
 true
 false
 
 
    阻塞队列以及阻塞队列的四种方法类型介绍到这里，实际的开发过程中，根据自己的业务场景来选择具体的方法类型，好的，下篇见。

1.队列介绍
 
今天要来讲一下java里的队列，队列，顾名思义，排队的列，既然按排队形来做的话，生活中的银行排队啊，上车排队啊，都是先到先办理或者先上车，队列存取数据列也一样，这就是先进先出，使用队列的规则是：使用队素时，数据元素只能从表的一端进入队列，另一端出队列。
 
 
称进入队列的一端为“队尾”，出队列的一端为“队头”。数据元素全部从队尾陆续进队列，由对头陆续出队列。
 
特点：先进先出
 
效率：插入数据项和移除数据项的时间复杂度都是O(1)，因为插入是一个一个而且只能在一端插入，取出也只能一个一个从一头取，这样不用循环一次取一次存就可以得到复杂度就是O(1)。
 
2.java的阻塞队列
 
2.1 ArrayBlockingQueue
 
基于数组实现的一个有界的阻塞队列，在创建ArrayBlockingQueue对象时必须指定容器大小。并且可以指定公平性和非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。
 
为什么是有界的?
 
看下图不指定容量会报错，那么指定了容量就是有界的。
 
 
为什么可以支持公平锁和非公平锁？
 
我随便拿个示例调用一个队列里的一个方法点进去
 
 
用的是ReentrantLock，ReentrantLock本身的功能是有支持公平锁和非公平锁的
 
 
下面代码示例下ArrayBlockingQueue怎么使用？
 
因为ArrayBlockingQueue存储和移除数据有三种情况，异常，阻塞，非阻塞
 
异常示例
 
先演示存储满了再进行存储异常的情况
 
public class BlockingQueueDemo {
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);
    //生产者
    class Producer extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < queueSize + 1; i++) {
                queue.add(i);
                System.out.println("向队列中添加元素，队列剩余空间：" + (queueSize - queue.size()));

            }
        }
    }
    
    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        Producer producer = blockingQueueDemo.new Producer();
        producer.start();
    }
}

​
 
我指定了存储10个数字，然后我要存储11个，那么就会报错，可以看出add()方法是存储满了就抛异常的方式
 
 
再来一个取元素，元素没有了，抛异常的代码情况
 
public class BlockingQueueDemo {
    
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);


    class costormer extends Thread {
        @Override
        public void run() {
            queue.remove();
            System.out.println("向队列中取出一个元素，队列剩余：" + queue.size() + "个元素");
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        costormer costormer = blockingQueueDemo.new costormer();
        costormer.start();
    }
}
 
队列里一个数据都没有，获取元素抛出没有元素异常,由此可见remove()是获取数据抛异常的方式
 
 
以上是异常的情况。
 
阻塞示例
 
public class BlockingQueueDemo {

    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    //生产者
    class Producer extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < queueSize + 1; i++) {

                try {
                    queue.put(i);
                    System.out.println("向队列中添加元素，队列剩余空间：" + (queueSize - queue.size()));
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        Producer producer = blockingQueueDemo.new Producer();
        producer.start();
    }
}
 
可以看到存储满了就会一直阻塞等待，直到队列元素被取出才会停止阻塞，由此可见存储数据的put()是有阻塞功能的。
 
 
取元素阻塞示例
 
public class BlockingQueueDemo {

    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    class costormer extends Thread {
        @Override
        public void run() {
            try {
                queue.take();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("向队列中取出一个元素，队列剩余：" + queue.size() + "个元素");
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        costormer costormer = blockingQueueDemo.new costormer();
        costormer.start();
    }
 
当前队列一个元素没有，取数据的时候就被阻塞一直等待了，程序一直没有退出操作，由此可见take()是取出阻塞操作的
 
 
非阻塞示例
 
public class BlockingQueueDemo {
    
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    //生产者
    class Producer extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < queueSize + 1; i++) {
                Boolean issuccess = queue.offer(i);
                if (issuccess) {
                    System.out.println("向队列中添加元素，队列剩余空间：" + (queueSize - queue.size()));
                } else {
                    System.out.println("队列已满！");
                }
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        Producer producer = blockingQueueDemo.new Producer();
        producer.start();
    }
}
 
区别相信大家也看出来了，满了的情况不会抛出异常，也不会阻塞，这种就是成功存储就返回true，队列满了不能存储就返回false了。
 
 
取数据非阻塞示例
 
public class BlockingQueueDemo {

    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    class costormer extends Thread {
        @Override
        public void run() {
            Object obj = queue.poll();
            if (obj == null) {
                System.out.println("队列无数据！");
            } else {
                System.out.println("向队列中取出一个元素，队列剩余：" + queue.size() + "个元素");
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        costormer costormer = blockingQueueDemo.new costormer();
        costormer.start();
    }
}
 
由此可见poll()方法是队列没有数据获取时不阻塞，不抛异常返回null的一种方式。
 
 
总结一下：
 
ArrayBlockingQueue异常：
 
 1.1 插入->队列满时再进行添加数据会抛出IllegalStateException异常。
 
      代表方法：add()
 
 1.2 移除->队列null时会抛出NoSuchElementException异常。
 
       代表方法：remove(),element()
 
ArrayBlockingQueue阻塞：
 
  1.1 插入->队列满再添加数据会堵塞
 
        代表方法：put()
 
  1.2 移除并获取->队列null时会堵塞
 
        代表方法：take()
 
ArrayBlockingQueue非阻塞：
 
  1.1 插入->队列满时再进行添加，就返回false
 
       代表方法：offer()
 
  1.2 移除并获取->队列为null,返回null
 
        代表方法：poll()，peek()
 
2.2 LinkedBlockingQueue
 
基于链表实现的一个可选有界阻塞队列，在创建LinkedBlockingQueue对象时如果不指定容量大小，则默认大小为Integer.MAX_VALUE。
 
 
数据结构从源码中看是单链表结构
 
 
阻塞、不阻塞、异常都是和ArrayBlockingQueue是一致的，这里就不在演示了
 
 
2.3 PriorityBlockingQueue
 
PriorityBlockingQueue的实现使用了基于数组的平衡二叉堆（小的在上，大的在下方，即最小堆）优先级阻塞队列，可选有界队列，它会按照元素的优先级对元素进行排序，按照优先级顺序出队，每次出队的元素都是优先级最高的元素。
 
在阻塞和不阻塞和异常都是跟上述方法一样，唯一不同的是优先级排序的实现方式上。大家可以自行学习，这里就不再介绍了
 
2.4 DelayQueue
 
DelayQueue比较特殊，它是一个BlockingQueue+PriorityQueue+Delayed的实现方式，可以这样说DelayQueue是使用了优先队列实现的BlockingQueue
 
一种延时阻塞队列，DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取该元素。DelayQueue是一个无界队列，因此往队列插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。
 
虽然DelayQueue中也有put这样的堵塞方法，但是put里调用的是没有进行阻塞offer的方法。
 
2.5 SynchronousQueue
 
SynchronousQueue的特点是只能容纳一个元素，同时SynchronousQueue使用了两种模式来管理元素，一种是使用先进先出的队列，一种是使用后进先出的栈，选用哪种模式可以通过构造函数来指定。(不常用)
 
3.java非阻塞队列
 
非阻塞队列实现方式是使用循环CAS,非阻塞队列和阻塞队列的区别就只是方法不同，阻塞id会有take等一些存储或获取阻塞的方法，非阻塞则没有阻塞的方法。
 
3.1 ArrayDeque
 
数组结构队列，底层数组实现，且双向操作，既可以向头添加数据也可以向尾添加数据，既可以头部取数据也可以尾部取数据。使用方式都和阻塞队列都一样
 
3.2  PriorityQueue
 
优先级非阻塞队列，方法都是类似的不多说了。
 
3.3 ConcurrentLinkedQueue
 
是基于链表的非阻塞队列，底层是通过链表来实现的，非阻塞方法和ArrayDeque类似，只是它只能向队列尾部添加数据，所以没有Last和First方法。
 
阻塞队列与非阻塞队列区别
 
阻塞队列可以阻塞，非阻塞队列不可以阻塞
阻塞队列当队列为空的时候从队列中获取元素的操作将会被阻塞，非阻塞队列为空的话，再从队列取出数据就直接返回null
阻塞队列当队列满了的话再插入数据就会被阻塞，直到队列不满
支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。
支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空。
非阻塞队列想要阻塞只能手动使用wait()和Notify()
其实大家自己代码测试的时候就可以发现，非阻塞的队列是没有阻塞的那些方法的
 
4.使用方法