【Java数据结构及算法实战】系列010：Java队列04——链表实现的阻塞队列LinkedBlockingQueue

LinkedBlockingQueue是一种基于链表实现的可选边界的阻塞队列，该队列排序元素FIFO。队列的队首是在该队列上停留时间最长的元素，队列的队尾是在该队列上停留最短时间的元素。在队列尾部插入新的元素，队列检索操作在队列的头部获取元素。

在大多数并发应用程序中，基于链表实现的队列通常具有比基于数组实现的队列更高的吞吐量，但性能上未必占优势。

LinkedBlockingQueue在初始化时可以指定容量也可以不指定容量。当初始化LinkedBlockingQueue指定容量时，是有界队列；当初始化LinkedBlockingQueue未指定容量时，其内部会以Integer.MAX_VALUE值作为容量。当然，因为Integer.MAX_VALUE值非常大，近似无限大，因此LinkedBlockingQueue未指定容量时也可以近似认为是无界队列。

为防止队列的过度的扩展，建议在LinkedBlockingQueue初始化时指定容量。LinkedBlockingQueue内部的链接节点在每次入队元素时动态创建，除非这会使队列超过容量。

LinkedBlockingQueue类及其迭代器实现了Collection和Iterator接口的所有可选方法。LinkedBlockingQueue是Java Collections Framework的一个成员。

1.   LinkedBlockingQueue的声明

LinkedBlockingQueue的接口和继承关系如下

public class LinkedBlockingQueue extends AbstractQueue

        implements BlockingQueue, java.io.Serializable {

   …

}

完整的接口继承关系如下图所示。

从上述代码可以看出，LinkedBlockingQueue既实现了BlockingQueue和java.io.Serializable接口，又继承了java.util.AbstractQueue。其中，AbstractQueue是Queue接口的抽象类，此处不再赘述。

2.   LinkedBlockingQueue的成员变量和构造函数

 

以下是LinkedBlockingQueue的构造函数和成员变量。

    // 容量

    private final int capacity;

    // 当前元素个数

    private final AtomicInteger count = new AtomicInteger();

    // 链表头结点

    // 不变式: head.item == null

    transient Node head;

    // 链表尾结点

    // 不变式: last.next == null

    private transient Node last;

    // 用于锁住take、poll等操作

    private final ReentrantLock takeLock = new ReentrantLock();

    // 队列非空，唤醒消费者

    private final Condition notEmpty = takeLock.newCondition();

    // 用于锁住put、offer等操作

    private final ReentrantLock putLock = new ReentrantLock();

    // 队列非满，唤醒生产者

private final Condition notFull = putLock.newCondition();

public LinkedBlockingQueue() {

        this(Integer.MAX_VALUE);

    }

    public LinkedBlockingQueue(int capacity) {

        if (capacity