Java集合--阻塞队列（LinkedBlockingQueue）

1. LinkedBlockingQueue

上篇中，说到了ArrayBlockingQueue阻塞队列。在ArrayBlockingQueue中，底层使用了数组结构来实现。

那么，提到数组了就不得不提及链表。作为两对成双成对的老冤家，链表也可以实现阻塞队列。

下面，就让我们进入今天的正题LinkedBlockingQueue！！！！

LinkedBlockingQueue是一个使用链表实现的阻塞队列，支持多线程并发操作，可保证数据的一致性。

与ArrayBlockingQueue相同的是，LinkedBlockingQueue也实现了元素“先进先出（FIFO）”规则，也使用ReentrantLock来保证数据的一致性；

与ArrayBlockingQueue不同的是，LinkedBlockingQueue通常被认为是“无界”的，在默认情况下LinkedBlockingQueue的链表长度为Integer.MAX_VALUE。

下面，我们就对LinkedBlockingQueue的原理具体分析分析！

(1)成员变量

对于ArrayBlockingQueue来说，当队列在进行入队和出队时，永远只能有一个操作被执行。因为该队列只有一把锁，所以在多线程执行中并不允许同时出队和入队。

与ArrayBlockingQueue不同的是，LinkedBlockingQueue拥有两把锁，一把读锁，一把写锁，可以在多线程情况下，满足同时出队和入队的操作。

在ArrayBlockingQueue中，由于出队入队使用了同一把锁，无论元素增加还是减少，都不会影响到队列元素数量的统计，所以使用了int类型的变量作为队列数量统计。

但是，在LinkedBlockingQueue中则不同。上面说了，在LinkedBlockingQueue中使用了2把锁，在同时出队入队时，都会涉及到对元素数量的并发修改，会有线程安全的问题。因此，在LinkedBlockingQueue中使用了原子操作类AtomicInteger，底层使用CAS（compare and set）来解决数据安全问题。

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    
    //队列容量大小，默认为Integer.MAX_VALUE
    private final int capacity;

    //队列中元素个数：(与ArrayBlockingQueue的不同)
    //出队和入队是两把锁
    private final AtomicInteger count = new AtomicInteger(0);

    //队列--头结点
    private transient Node<E> head;

    //队列--尾结点
    private transient Node<E> last;

    //与ArrayBlockingQueue的不同,两把锁
    //读取锁
    private final ReentrantLock takeLock = new ReentrantLock();

    //出队等待条件
    private final Condition notEmpty = takeLock.newCondition();

    //插入锁
    private final ReentrantLock putLock = new ReentrantLock();

    //入队等待条件
    private final Condition notFull = putLock.newCondition();
}

(2)链表结点

由于LinkedBlockingQueue是链表结构，所以必然会有结点存在。

结点中，保存这元素的值，以及本结点指向下一个结点的指针。

//队列存储元素的结点(链表结点):
static class Node<E> {
    //队列元素：
    E item;

    //链表中指向的下一个结点
    Node<E> next;

    //结点构造：
    Node(E x) { item = x; }
}

(3)构造函数

之前，我们说了LinkedBlockingQueue可以称为是无界队列，为什么是无界的，就是因为LinkedBlockingQueue的默认构造函数中，指定的队列大小为Integer.MAX_VALUE = 2147483647，想必没有哪个应用程序能达到这个数量。

在初始化中，LinkedBlockingQueue的头尾结点中的元素被置为null；

//默认构造函数：
public LinkedBlockingQueue() {
    //默认队列长度为Integer.MAX_VALUE
    this(Integer.MAX_VALUE);
}

//指定队列长度的构造函数：
public LinkedBlockingQueue(int capacity) {
    //初始化链表长度不能为0
    if (capacity <= 0) throw new IllegalArgumentException();
    this.capacity = capacity;
    //设置头尾结点，元素为null
    last = head = new Node<E>(null);
}

(4)插入元素（入队）

LinkedBlockingQueue的插入获取和ArrayBlockingQueue基本类似，都包含有阻塞式和非阻塞式。

put（E e）是阻塞式插入，如果队列中的元素与链表长度相同，则此线程等待，直到有空余空间时，才执行。

//向队列尾部插入元素：队列满了线程等待
public void put(E e) throws InterruptedException {
    //不能插入为null元素：
    if (e == null) throw new NullPointerException();
    int c = -1;
    //创建元素结点：
    Node<E> node = new Node(e);
    final ReentrantLock putLock = this.putLock;
    final AtomicInteger count = this.count;
    //加插入锁，保证数据的一致性：
    putLock.lockInterruptibly();
    try {
        //当队列元素个数==链表长度
        while (count.get() == capacity) {
            //插入线程等待：
            notFull.await();
        }
        //插入元素：
        enqueue(node);
        //队列元素增加：count+1,但返回+1前的count值：
        c = count.getAndIncrement();
        //容量还没满，唤醒生产者线程
        // (例如链表长度为5，此时第五个元素已经插入，c=4，+1=5，所以超过了队列容量，则不会再唤醒生产者线程)
        if (c + 1 < capacity)
            notFull.signal();
    } finally {
        //释放锁：
        putLock.unlock();
    }
    //当c=0时，即意味着之前的队列是空队列,消费者线程都处于等待状态，需要被唤醒进行消费
    if (c == 0)
        //唤醒消费者线程：
        signalNotEmpty();
}

offer(E e)是非阻塞式插入，队列中的元素与链表长度相同时，直接返回false,不会阻塞线程。

//向队列尾部插入元素：返回true/false
public boolean offer(E e) {
    //插入元素不能为空
    if (e == null) throw new NullPointerException();
    final AtomicInteger count = this.count;
    //如果队列元素==链表长度，则直接返回false
    if (count.get() == capacity)
        return false;
    int c = -1;
    //创建元素结点对象：
    Node<E> node = new Node(e);
    final ReentrantLock putLock = this.putLock;
    //加锁，保证数据一致性
    putLock.lock();
    try {
        //队列元素个数 小于 链表长度
        if (count.get() < capacity) {
            //向队列中插入元素：
            enqueue(node);
            //增加队列元素个数：
            c = count.getAndIncrement();
            //容量还没满，唤醒生产者线程：
            if (c + 1 < capacity)
                notFull.signal();
        }
    } finally {
        //释放锁：
        putLock.unlock();
    }
    //此时，代表队列中还有一条数据，可以进行消费，唤醒消费者线程
    if (c == 0)
        signalNotEmpty();
    return c >= 0;
}

(5)获取元素（出队）

take()：阻塞式出队，获取队列头部元素，如果队列中没有元素，则此线程的等待，直到队列中有元素才执行。

//从队列头部获取元素，并返回。队列为null，则一直等待
public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    //设置读取锁：
    takeLock.lockInterruptibly();
    try {
        //如果此时队列为空，则获取线程等待
        while (count.get() == 0) {
            notEmpty.await();
        }
        //从队列头部获取元素：
        x = dequeue();
        //减少队列元素-1,返回count减少前的值；
        c = count.getAndDecrement();
        //队列中还有可以消费的元素，唤醒其他消费者线程
        if (c > 1)
            notEmpty.signal();
    } finally {
        //释放锁：
        takeLock.unlock();
    }
    //队列中出现了空余元素，唤醒生产者进行生产。
    // (链表长度为5，队列在执行take前有5个元素，执行到此处时候有4个元素了，但是c的值还是5，所以会进入到if中来)
    if (c == capacity)
        signalNotFull();
    return x;
}

poll()：非阻塞式出队，当队列中没有元素，则返回null.

//获取头部元素，并返回。队列为空，则直接返回null
public E poll() {
    final AtomicInteger count = this.count;
    //如果队列中还没有元素，则直接返回 null
    if (count.get() == 0)
        return null;
    E x = null;
    int c = -1;
    final ReentrantLock takeLock = this.takeLock;
    //加锁，保证数据的安全
    takeLock.lock();
    try {
        //此时在判断，队列元素是否大于0
        if (count.get() > 0) {
            //移除队头元素
            x = dequeue();
            //减少队列元素个数
            c = count.getAndDecrement();
            //此时队列中，还有1个元素，唤醒消费者线程继续执行
            if (c > 1)
                notEmpty.signal();
        }
    } finally {
        //释放锁：
        takeLock.unlock();
    }
    //队列中出现了空余元素，唤醒生产者进行生产。
    // (链表长度为5，队列在执行take前有5个元素，执行到此处时候有4个元素了，但是c的值还是5，所以会进入到if中来)
    if (c == capacity)
        signalNotFull();
    return x;
}

(6)出队入队图片介绍

入队

入队操作，很简单，就是向链表中逐个插入新的元素！

[图片上传失败...(image-cf7641-1512918370979)]

首先，将最后的结点指向新插入的结点，其次将last结点置为新插入的结点，流程结束！

出队

相比于入队来说，出队的情况要复杂一点点！

但是，请记住一点，就是头部元素永远为null！

[图片上传失败...(image-a955df-1512918370979)]

首先，将头部元素的指向下一个结点的引用，只向自己，主要为了GC的快速清理！

再将，队列中的第一个元素变成头结点，而头结点又保有永远为null的属性，则将头结点元素置为null，也就是出队操作！

(7)ArrayBlockingQueue与LinkedBlockingQueue对比

ArrayBlockingQueue底层基于数组实现，需要使用者指定队列长度，是一个不折不扣的有界队列。

LinkedBlockingQueue底层基于链表实现，无需使用者指定队列长度（可自定义)，当使用默认大小时候，是一个无界队列。

ArrayBlockingQueue由于默认必须设置队列长度，所以在使用时会能更好的预测系统性能；而LinkedBlockingQueue默认无参构造，无需指定队列长度，所以在使用时一定要多加注意，当队列中元素短时间内暴增时，可能会对系统产生灾难性影响。

但是，LinkedBlockingQueue的一大优点也是ArrayBlockingQueue所不具备的，那么就是在多个CPU的情况下，LinkedBlockingQueue可以做到同一时刻既消费、又生产。故LinkedBlockingQueue的性能也要优于ArrayBlockingQueue。

（8）生产者消费者实现

使用LinkedBlockingQueue简单模拟消费者生产者实现；

public class LinkedBlockingQueueTest {

    static class Apple{

        String colour;

        public Apple(String colour){
            this.colour = colour;
        }

        public String getColour() {
            return colour;
        }

        public void setColour(String colour) {
            this.colour = colour;
        }
    }

    //生产者
    static class Producer implements Runnable{

        LinkedBlockingQueue<Apple> queueProducer ;

        Apple apple;

        public Producer( LinkedBlockingQueue<Apple> queueProducer,Apple apple){
            this.queueProducer = queueProducer;
            this.apple = apple;
        }

        public void run() {
            try {
                System.out.println("生产"+apple.getColour()+"的苹果");
                queueProducer.put(apple);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }


    //消费者
    static class Consumer implements Runnable{

        LinkedBlockingQueue<Apple> queueConsumer ;

        public Consumer(LinkedBlockingQueue<Apple> queueConsumer){
            this.queueConsumer = queueConsumer;
        }

        public void run() {
            try {
                Apple apple = queueConsumer.take();
                System.out.println("消费"+apple.getColour()+"的苹果");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        LinkedBlockingQueue<Apple> queue = new LinkedBlockingQueue<Apple>();

        Apple appleRed = new Apple("红色");
        Apple appleGreen = new Apple("绿色");

        Producer producer1 = new Producer(queue,appleRed);

        Producer producer2 = new Producer(queue,appleGreen);

        Consumer consumer = new Consumer(queue);

        producer1.run();
        producer2.run();
        consumer.run();

        Thread.sleep(10000);
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,362评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,330评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,247评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,560评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,580评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,569评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,929评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,587评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,840评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,596评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,678评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,366评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,945评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,929评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,165评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,271评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,403评论 2赞 342