多线程和并发编程（4）—并发数据结构之BlockingQueue

队列(Queue)就是一种满足先进先出（FIFO）特性的数据结构。Java中阻塞队列(BlockingQueue)具有当队列满了再添加元素则会阻塞，当队列空了再获取元素则会阻塞的特性。

一、队列数据结构

1.Queen接口

public interface Queue<E> extends Collection<E> {
   
    //添加一个元素，添加成功返回true, 如果队列满了，就会抛出异常
    boolean add(E e);
    //添加一个元素，添加成功返回true, 如果队列满了，返回false
    boolean offer(E e);
    //返回并删除队首元素，队列为空则抛出异常
    E remove();
    //返回并删除队首元素，队列为空则返回null
    E poll();
    //返回队首元素，但不移除，队列为空则抛出异常
    E element();
    //获取队首元素，但不移除，队列为空则返回null
    E peek();
}

2.使用场景

• 线程池

线程池中的任务队列通常是一个阻塞队列。当任务数超过线程池的容量时，新提交的任务将被放入任务队列中等待执行。线程池中的工作线程从任务队列中取出任务进行处理，如果队列为空，则工作线程会被阻塞，直到队列中有新的任务被提交。

• 生产者-消费者模型

在生产者-消费者模型中，生产者向队列中添加元素，消费者从队列中取出元素进行处理。阻塞队列可以很好地解决生产者和消费者之间的并发问题，避免线程间的竞争和冲突。

• 消息队列

消息队列使用阻塞队列来存储消息，生产者将消息放入队列中，消费者从队列中取出消息进行处理。消息队列可以实现异步通信，提高系统的吞吐量和响应性能，同时还可以将不同的组件解耦，提高系统的可维护性和可扩展性。

总之，阻塞队列在实际应用中有很多场景，它可以帮助我们解决并发问题，提高程序的性能和可靠性。

二、JUC中的BlockingQueue实现

1. ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列
2. LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列
3. PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列
4. DelayQueue：一个使用优先级队列实现的延时无界阻塞队列
5. SynchronousQueue：一个不存储元素的阻塞队列
6. LinkedTransferQueue：一个由链表结构组成的无界阻塞队列（实现了继承于 BlockingQueue 的 TransferQueue）
7. LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列

1.ArrayBlockingQueue

public class BlockingQueueTest {
   
    public static void main(String[] args) throws InterruptedException {
   
        BlockingQueue<String> queue = new ArrayBlockingQueue(1024);
        queue.put("aaa");
        System.out.println(queue);
        queue.take();
        System.out.println(queue);
        }
    }

ArrayBlockingQueue使用独占锁ReentrantLock实现线程安全，入队和出队操作使用同一个锁对象，也就是只能有一个线程可以进行入队或者出队操作；这也就意味着生产者和消费者无法并行操作，在高并发场景下会成为性能瓶颈。利用了Lock锁的Condition通知机制进行阻塞控制。

//todo 源码分析

2.LinkedBlockingQueue

public class BlockingQueueTest {
    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<String> queue = new LinkedBlockingQueue<String>(10);
        System.out.println(queue);
        queue.put("bbb");
        System.out.println(queue);
        queue.take();
        }
    }

LinkedBlockingQueue是一个基于链表实现的阻塞队列，默认情况下，该阻塞队列的大小为Integer.MAX_VALUE，由于这个数值特别大，所以 LinkedBlockingQueue 也被称作无界队列，代表它几乎没有界限，队列可以随着元素的添加而动态增长，但是如果没有剩余内存，则队列将抛出OOM错误。所以为了避免队列过大造成机器负载或者内存爆满的情况出现，我们在使用的时候建议手动传一个队列的大小。

LinkedBlockingQueue与ArrayBlockingQueue对比

1. ArrayBlockingQueue和LinkedBlockingQueue都是基于ReentrantLock锁机制和Condition条件通知机制来实现阻塞队列的。

2. 队列大小有所不同，ArrayBlockingQueue是有界的初始化必须指定大小，而LinkedBlockingQueue可以是有界的也可以是无界的(Integer.MAX_VALUE)，对于后者而言，当添加速度大于移除速度时，在无界的情况下，可能会造成内存溢出等问题。

3. 数据存储容器不同，ArrayBlockingQueue采用的是数组作为数据存储容器，而LinkedBlockingQueue采用的则是以Node节点作为连接对象的链表。对ArrayBlockingQueue的数组进行加锁来实现阻塞，只声明一把锁即可，对LinkedBlockingQueue的头结点和尾结点进行加锁，需要声明两把锁，这点区别导致LinkedBlockingQueue有更好的并发性能。

3.PriorityBlockingQueue

集合中无界优先队列priorityBlockingQueue内部使用堆算法保证每次出队都是优先级最高的元素。添加的元素需要实现comparable接口。

4.DelayQueue

DelayQueue 是一个支持延时获取元素的阻塞队列， 内部采用优先队列 PriorityQueue 存储元素，同时元素必须实现 Delayed 接口；在创建元素时可以指定多久才可以从队列中获取当前元素，只有在延迟期满时才能从队列中提取元素。延迟队列的特点是：不是先进先出，而是会按照延迟时间的长短来排序，下一个即将执行的任务会排到队列的最前面。

它是无界队列，放入的元素必须实现 Delayed 接口，而 Delayed 接口又继承了 Comparable 接口，所以自然就拥有了比较和排序的能力。

public interface Delayed extends Comparable<Delayed> {
   
    //getDelay 方法返回的是“还剩下多长的延迟时间才会被执行”，
    //如果返回 0 或者负数则代表任务已过期。
    //元素会根据延迟时间的长短被放到队列的不同位置，越靠近队列头代表越早过期。
    long getDelay(TimeUnit unit);
}