死磕Java并发：J.U.C之阻塞队列：LinkedBlockingDeque

作者：chenssy  

来源：Java技术驿站

前面的BlockingQueue都是单向的FIFO队列，而LinkedBlockingDeque则是一个由链表组成的双向阻塞队列，双向队列就意味着可以从对头、对尾两端插入和移除元素，同样意味着LinkedBlockingDeque支持FIFO、FILO两种操作方式。

LinkedBlockingDeque是可选容量的，在初始化时可以设置容量防止其过度膨胀，如果不设置，默认容量大小为Integer.MAX_VALUE。

LinkedBlockingDeque

LinkedBlockingDeque 继承AbstractQueue，实现接口BlockingDeque，而BlockingDeque又继承接口BlockingQueue，BlockingDeque是支持两个附加操作的 Queue，这两个操作是：获取元素时等待双端队列变为非空；存储元素时等待双端队列中的空间变得可用。这两类操作就为LinkedBlockingDeque 的双向操作Queue提供了可能。

BlockingDeque接口提供了一系列的以First和Last结尾的方法，如addFirst、addLast、peekFirst、peekLast。

1. public class LinkedBlockingDeque<E>

2.    extends AbstractQueue<E>

3.    implements BlockingDeque<E>, java.io.Serializable {

5.    // 双向链表的表头

6.    transient Node<E> first;

8.    // 双向链表的表尾

9.    transient Node<E> last;

11.    // 大小，双向链表中当前节点个数

12.    private transient int count;

14.    // 容量，在创建LinkedBlockingDeque时指定的

15.    private final int capacity;

17.    final ReentrantLock lock = new ReentrantLock();

19.    private final Condition notEmpty = lock.newCondition();

21.    private final Condition notFull = lock.newCondition();

23. }

通过上面的Lock可以看出，LinkedBlockingDeque底层实现机制与LinkedBlockingQueue一样，依然是通过互斥锁ReentrantLock 来实现，notEmpty 、notFull 两个Condition做协调生产者、消费者问题。

与其他BlockingQueue一样，节点还是使用内部类Node：

1.    static final class Node<E> {

2.        E item;

4.        Node<E> prev;

6.        Node<E> next;

8.        Node(E x) {

9.            item = x;

10.        }

11.    }

双向嘛，节点肯定得要有前驱prev、后继next咯。

基础方法

LinkedBlockingDeque 的add、put、offer、take、peek、poll系列方法都是通过调用XXXFirst，XXXLast方法。所以这里就仅以putFirst、putLast、pollFirst、pollLast分析下。

• putFirst

putFirst(E e) :将指定的元素插入此双端队列的开头，必要时将一直等待可用空间。

1.    public void putFirst(E e) throws InterruptedException {

2.        // check null

3.        if (e == null) throw new NullPointerException();

4.        Node<E> node = new Node<E>(e);

5.        // 获取锁

6.        final ReentrantLock lock = this.lock;

7.        lock.lock();

8.        try {

9.            while (!linkFirst(node))

10.                // 在notFull条件上等待，直到被唤醒或中断

11.                notFull.await();

12.        } finally {

13.            // 释放锁

14.            lock.unlock();

15.        }

16.    }

先获取锁，然后调用linkFirst方法入列，最后释放锁。如果队列是满的则在notFull上面等待。linkFirst设置Node为对头：

1.    private boolean linkFirst(Node<E> node) {

2.        // 超出容量

3.        if (count >= capacity)

4.            return false;

6.        // 首节点

7.        Node<E> f = first;

8.        // 新节点的next指向原first

9.        node.next = f;

10.        // 设置node为新的first

11.        first = node;

13.        // 没有尾节点，设置node为尾节点

14.        if (last == null)

15.            last = node;

16.        // 有尾节点，那就将之前first的pre指向新增node

17.        else

18.            f.prev = node;

19.        ++count;

20.        // 唤醒notEmpty

21.        notEmpty.signal();

22.        return true;

23.    }

linkFirst主要是设置node节点队列的列头节点，成功返回true，如果队列满了返回false。整个过程还是比较简单的。

• putLast

putLast(E e) :将指定的元素插入此双端队列的末尾，必要时将一直等待可用空间。

1.    public void putLast(E e) throws InterruptedException {

2.        if (e == null) throw new NullPointerException();

3.        Node<E> node = new Node<E>(e);

4.        final ReentrantLock lock = this.lock;

5.        lock.lock();

6.        try {

7.            while (!linkLast(node))

8.                notFull.await();

9.        } finally {

10.            lock.unlock();

11.        }

12.    }

调用linkLast将节点Node链接到队列尾部：

1.    private boolean linkLast(Node<E> node) {

2.        if (count >= capacity)

3.            return false;

4.        // 尾节点

5.        Node<E> l = last;

7.        // 将Node的前驱指向原本的last

8.        node.prev = l;

10.        // 将node设置为last

11.        last = node;

12.        // 首节点为null，则设置node为first

13.        if (first == null)

14.            first = node;

15.        else

16.        //非null，说明之前的last有值，就将之前的last的next指向node

17.            l.next = node;

18.        ++count;

19.        notEmpty.signal();

20.        return true;

21.    }

• pollFirst

pollFirst()：获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。

1.    public E pollFirst() {

2.        final ReentrantLock lock = this.lock;

3.        lock.lock();

4.        try {

5.            return unlinkFirst();

6.        } finally {

7.            lock.unlock();

8.        }

9.    }

调用unlinkFirst移除队列首元素：

1.    private E unlinkFirst() {

2.        // 首节点

3.        Node<E> f = first;

5.        // 空队列，直接返回null

6.        if (f == null)

7.            return null;

9.        // first.next

10.        Node<E> n = f.next;

12.        // 节点item

13.        E item = f.item;

15.        // 移除掉first ==> first = first.next

16.        f.item = null;

17.        f.next = f; // help GC

18.        first = n;

20.        // 移除后为空队列，仅有一个节点

21.        if (n == null)

22.            last = null;

23.        else

24.        // n的pre原来指向之前的first，现在n变为first了，pre指向null

25.            n.prev = null;

26.        --count;

27.        notFull.signal();

28.        return item;

29.    }

• pollLast

pollLast():获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。

1.    public E pollLast() {

2.        final ReentrantLock lock = this.lock;

3.        lock.lock();

4.        try {

5.            return unlinkLast();

6.        } finally {

7.            lock.unlock();

8.        }

9.    }

调用unlinkLast移除尾结点，链表空返回null ：

1.    private E unlinkLast() {

2.        // assert lock.isHeldByCurrentThread();

3.        Node<E> l = last;

4.        if (l == null)

5.            return null;

6.        Node<E> p = l.prev;

7.        E item = l.item;

8.        l.item = null;

9.        l.prev = l; // help GC

10.        last = p;

11.        if (p == null)

12.            first = null;

13.        else

14.            p.next = null;

15.        --count;

16.        notFull.signal();

17.        return item;

18.    }

LinkedBlockingDeque大部分方法都是通过linkFirst、linkLast、unlinkFirst、unlinkLast这四个方法来实现的，因为是双向队列，所以他们都是针对first、last的操作，看懂这个整个LinkedBlockingDeque就不难了。

掌握了双向队列的插入、删除操作，LinkedBlockingDeque就没有任何难度可言了，数据结构的重要性啊！！！！

-END-

 近期热文：

• JIRA配置手册 （3）：字段和界面
  

• JIRA配置手册 （2）：工作流

• JIRA配置手册 （1）：问题类型管理

• HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！

• 你真的了解lambda吗？一文让你明白lambda用法与源码分析

• 程序员格斗指南

• 设计RPC接口时，你有考虑过这些吗？

• 阿里巴巴硅谷 Istio 专家解读Istio 1.0 发布

• 如何用图像识别玩忍术？

• 来自95后的天池中间件大赛总结

• 为Spring Cloud Config插上管理的翅膀
  

• Spring Cloud Config采用Git存储时两种常用的配置策略

• Hystrix降级逻辑中如何获取触发的异常？

• 重磅剧透！阿里巴巴计划开源 Nacos，为Dubbo生态发展铺路

• Spring Cloud Config采用数据库存储配置内容

• 你可能会忽略的 Git 提交规范

• SpringBoot应用部署于外置Tomcat容器

关注我

点击“阅读原文”，看本号其他精彩内容