BlockingDeque之LinkedBlockingDeque

╰半夏微凉° 2022-09-01 14:56 126阅读 0赞

> **关键词：**BlockingDeque    LinkedBlockingDeque    Deque

--------------------

**JDK**中对**BlockingDeque**的实现，只提供了**LinkedBlockingDeque**基于**链表**的实现方式。个人的猜测是因为双端队列基于数组实现的话会比较复杂，数组不适合作为双端队列的实现结构。*（学习LinkedBlockingDeque前，建议先了解BlockingDeque，请戳《[JUC之BlockingDeque双端队列][JUC_BlockingDeque]》）*

# **█ **LinkedBlockingDeque #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 1][]

### 字段： ###

transient Node<E> first;
    
    transient Node<E> last;
    
    private transient int count;
    
    private final int capacity;
    
    final ReentrantLock lock = new ReentrantLock();
    
    private final Condition notEmpty = lock.newCondition();
    
    private final Condition notFull = lock.newCondition();

*  **first**

队列中的第一个元素节点，即队首的第一个元素节点。

**Node**类型的字段，Node是LinkedBlockingDeque中定义的内部类，从定义来看，Node构成的链表是**双向链表**。

static final class Node<E> {
        // 节点对应的元素 
        E item;
        // 该节点的前驱节点
        Node<E> prev;
        // 该节点的后驱节点
        Node<E> next;
    
        Node(E x) {
            item = x;
        }
    }

![20210728215544724.png][]

*  **last**

队列中的最后一个元素节点，即队尾的第一个元素节点。

*  **count**

队列中存在的元素个数。

*  **capacity**

队列的容量，即队列最多能存放的元素个数。

*  **lock**

使用**ReentrantLock**来保证线程安全。

*  **notEmpty**

使用ReentrantLock的**Condition**完成线程间的通信，通知正在阻塞等待移出数据的线程，队列不为空了。

*  **notFull**

通知正在阻塞等待添加数据的线程，队列没有满。

### 构造器： ###

public LinkedBlockingDeque() {
        this(Integer.MAX_VALUE);
    }

public LinkedBlockingDeque(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
    }

public LinkedBlockingDeque(Collection<? extends E> c) {
        this(Integer.MAX_VALUE);
        final ReentrantLock lock = this.lock;
        lock.lock(); // Never contended, but necessary for visibility
        try {
            for (E e : c) {
                if (e == null)
                    throw new NullPointerException();
                if (!linkLast(new Node<E>(e)))
                    throw new IllegalStateException("Deque full");
            }
        } finally {
            lock.unlock();
        }
    }

**①**在构造器中对队列的容量进行初始化，且容量值必须为大于0的正数。

**②**默认的容量为**Integer.MAX\_VALUE**。

**③**当使用**Collection**初始化队列时，集合中不能含有null元素而且集合中元素的个数不能超过队列的容量，即Integer.MAX\_VALUE。

### 方法： ###

*（方法都是对**BlockingDeque**或**Deque**中定义的方法的实现，关于方法具体具有的行为约束，请戳《[JUC之BlockingDeque双端队列][JUC_BlockingDeque]》）*

**1、**向队列中添加元素（不具有阻塞等待功能）

*  **offerFirst**

向队首添加元素，如果队列满了没有足够的空间继续添加元素，则元素添加失败，返回false。

public boolean offerFirst(E e) {
        // 限制元素不能为null
        if (e == null) throw new NullPointerException();
        // 将元素封装成Node对象
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkFirst(node);
        } finally {
            lock.unlock();
        }
    }

**linkFirst：**

将first指向新添加的元素节点，新元素节点的**next**指向原来链表的第一个元素节点，该原来链表的第一个元素节点的**prev**指向该新元素节点，以此形成新的链表。linkFirst永远将元素节点链接到链表的头节点。（不同于其他基于链表方式实现的类，如**LinkedList**、**AQS**中的等待队列。他们在实现链表的时候，链表的第一个节点一直是空的节点，即不存放元素的节点，而LinkedBlockingDeque显然不是）

private boolean linkFirst(Node<E> node) {
        // count为队列中元素的个数，capacity为队列的容量
        if (count >= capacity)
            return false;
        // f为原先的队首节点    
        Node<E> f = first;
        // 新节点的next指针指向原先的队首节点
        node.next = f;
        // 队首指针指向新节点，即将新节点作为队首节点
        first = node;
        // last==null，即队列中没有元素，这是向队列中添加的第一个元素
        if (last == null)
            last = node;
        // 将原先的队首节点前驱指针指向新的队首节点，
        // 这样新的队首节点就与链表链接上了
        else
            f.prev = node;
        // 标记队列中元素的数量的值+1    
        ++count;
        // 通知正在等待阻塞从队列中移出值的线程
        notEmpty.signal();
        return true;
    }

**（1）**向空的队列第一次添加元素，此时first、last都为null。

**①**Node<E> f = first;

![20210728220009933.png][]

**②**node.next = f;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 2][]

**③**first = node;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 3][]

**④**last = node;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 4][]

**（2）**向已有元素的队列中添加，此时first、last都不为null。

**①**Node<E> f = first;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 5][]

**②**node.next = f;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 6][]

**③**first = node;

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 7][]

**④**f.prev = node

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 8][]

*  **offerLast**

向队尾添加元素，如果队列满了没有足够的空间继续添加元素，则元素添加失败，返回false。

public boolean offerLast(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return linkLast(node);
        } finally {
            lock.unlock();
        }
    }

**linkLast：**

与linkFirst不同的地方就在于，linkLast是将last指针指向新的元素节点。新的元素节点是一直向链表的尾部添加。

private boolean linkLast(Node<E> node) {
        // assert lock.isHeldByCurrentThread();
        if (count >= capacity)
            return false;
        Node<E> l = last;
        node.prev = l;
        last = node;
        if (first == null)
            first = node;
        else
            l.next = node;
        ++count;
        notEmpty.signal();
        return true;
    }

*  **addFirst**

向队首添加元素，如果队列满了，则抛出**new IllegalStateException("Deque full")**异常。addFirst的实现借助了offerFirst。

public void addFirst(E e) {
        if (!offerFirst(e))
            throw new IllegalStateException("Deque full");
    }

*  **addLast**

向队尾添加元素，如果队列满了，则抛出**new IllegalStateException("Deque full")**异常。addLast的实现借助了offerLast。

public void addLast(E e) {
        if (!offerLast(e))
            throw new IllegalStateException("Deque full");
    }

*  **offer**

向队尾添加元素，等价于offerLast*（从其实现代码可以看出，是直接调用了offerLast）*。

public boolean offer(E e) {
        return offerLast(e);
    }

*  **add**

向队尾添加元素，等价于addLast。如果队列满了无法继续添加元素，则addLast会抛出异常，add会继续将异常抛出。

public boolean add(E e) {
        addLast(e);
        return true;
    }

*  **push**

向队首添加元素。等价于addFirst。

public void push(E e) {
        addFirst(e);
    }

**2、**移出队列中的元素（不具有阻塞等待功能）

*  **pollFirst**

移出队首的第一个元素，如果队列为空，则返回null。

public E pollFirst() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return unlinkFirst();
        } finally {
            lock.unlock();
        }
    }

**unlinkFirst：**

将first指向的元素节点与链表断开连接并返回，然后将first指向原先队首的第二个元素节点，让该元素节点称为新的队首第一个元素节点。

private E unlinkFirst() {
        Node<E> f = first;
        // f==null表示此时队列为空
        if (f == null)
            return null;
        // n为队首的第二个元素    
        Node<E> n = f.next;
        // 经过下面三行代码，会将队首的第一个元素从链表断开
        E item = f.item;
        f.item = null;
        f.next = f;
        // first指向原来队首的第二个元素
        first = n;
        if (n == null)
            last = null;
        else
            n.prev = null;
        --count;
        notFull.signal();
        return item;
    }

*  **pollLast**

移出队尾的第一个元素。如果队列为空，则返回null。

public E pollLast() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return unlinkLast();
        } finally {
            lock.unlock();
        }
    }

**unlinkLast：**

将last指向的元素节点与链表断开连接并返回，然后将last指向原先队尾的第二个元素节点，让该元素节点称为新的队尾第一个元素节点。

private E unlinkLast() {
        // assert lock.isHeldByCurrentThread();
        Node<E> l = last;
        if (l == null)
            return null;
        Node<E> p = l.prev;
        E item = l.item;
        l.item = null;
        l.prev = l; // help GC
        last = p;
        if (p == null)
            first = null;
        else
            p.next = null;
        --count;
        notFull.signal();
        return item;
    }

*  **removeFirst**

移出队首的第一个元素，如果队列为空，则抛出**NoSuchElementException**异常。removeFirst的实现借助了pollFirst。

public E removeFirst() {
        E x = pollFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

*  **removeLast**

移出队尾的第一个元素，如果队列为空，则抛出NoSuchElementException异常。

public E removeLast() {
        E x = pollLast();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

*  **poll**

移出队首的第一个元素，等价于pollFirst。

public E poll() {
        return pollFirst();
    }

*  **remove**

移出队首的第一个元素，等价于removeFirst。

public E remove() {
        return removeFirst();
    }

*  **pop**

等价于removeFirst。

public E pop() {
        return removeFirst();
    }

**3、**查看队首、队尾元素

*  **peekFirst**

获取队首的第一个元素，如果队列为空，则返回null。该方法只查看却不移出元素。

public E peekFirst() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return (first == null) ? null : first.item;
        } finally {
            lock.unlock();
        }
    }

*  **peekLast**

获取队尾的第一个元素，如果队列为空，则返回null。该方法只查看却不移出元素。

public E peekLast() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return (last == null) ? null : last.item;
        } finally {
            lock.unlock();
        }
    }

*  **getFirst**

获取队首的第一个元素，如果队列为空，则抛出NoSuchElementException异常。

public E getFirst() {
        E x = peekFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

*  **getLast**

获取队尾的第一个元素，如果队列为空，则抛出NoSuchElementException异常。

public E getLast() {
        E x = peekLast();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

*  **peek**

获取队首的第一个元素，等价于peekFirst。

public E peek() {
        return peekFirst();
    }

*  **element**

获取队首的第一个元素，如果队列为空，则抛出NoSuchElementException异常。

public E element() {
        return getFirst();
    }

** getFirst：**

public E getFirst() {
        E x = peekFirst();
        if (x == null) throw new NoSuchElementException();
        return x;
    }

**4、**向队列中添加元素（具有阻塞等待功能）

*  **putFirst**

向队首添加元素，当队列满了无法继续添加元素时，该方法会一直阻塞，直到队列有空间可以添加该元素了。while (!linkFirst(node)) notFull.await();使用while循环去调用linkFirst尝试向队首添加元素，如果添加失败就调用notFull.await()让当前线程休眠。直到其他线程调用了从队列中移出元素时，会调用notFull.signal()方法唤醒该线程，继续尝试添加元素到队首。

public void putFirst(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        // 将元素封装成Node对象
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            while (!linkFirst(node))
                notFull.await();
        } finally {
            lock.unlock();
        }
    }

*  **putLast**

和putFirst相似，不同的是向队尾添加元素。

public void putLast(E e) throws InterruptedException {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            while (!linkLast(node))
                notFull.await();
        } finally {
            lock.unlock();
        }
    }

*  **offerFirst**

具有超时阻塞等待的向队首添加元素。在达到超时等待时长时，如果还没有添加元素成功，则返回false。

public boolean offerFirst(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (!linkFirst(node)) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

*  **offerLast**

与offerFirst相似，不同的是其是向队尾添加元素。

public boolean offerLast(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
        if (e == null) throw new NullPointerException();
        Node<E> node = new Node<E>(e);
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (!linkLast(node)) {
                if (nanos <= 0)
                    return false;
                nanos = notFull.awaitNanos(nanos);
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

*  **put**

等价于putLast。

public void put(E e) throws InterruptedException {
        putLast(e);
    }

*  **offer**

等价于offerLast。

**5、**从队列中移出元素（具有阻塞等待功能）

*  **takeFirst**

移出队首的第一个元素，如果元素为空，则会一直阻塞等待，直到队首有元素可以移出。

public E takeFirst() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E x;
            while ( (x = unlinkFirst()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

*  **takeLast**

与takeFirst相似，不同在于其是移出队尾的第一个元素。

public E takeLast() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E x;
            while ( (x = unlinkLast()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

*  **pollFirst**

具有超时阻塞等待的从队首移出第一个元素，如果超过了阻塞等待时长，队列还为空，则返回null。

public E pollFirst(long timeout, TimeUnit unit)
        throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            E x;
            while ( (x = unlinkFirst()) == null) {
                if (nanos <= 0)
                    return null;
                nanos = notEmpty.awaitNanos(nanos);
            }
            return x;
        } finally {
            lock.unlock();
        }
    }

*  **pollLast**

与pollFirst相似，不同的是其是移出队尾的第一个元素。

public E pollLast(long timeout, TimeUnit unit)
        throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            E x;
            while ( (x = unlinkLast()) == null) {
                if (nanos <= 0)
                    return null;
                nanos = notEmpty.awaitNanos(nanos);
            }
            return x;
        } finally {
            lock.unlock();
        }
    }

*  **take**

等价于takeFirst。

public E take() throws InterruptedException {
        return takeFirst();
    }

**6、**其他方法

*  **removeFirstOccurrence**

从队首遍历，移出第一个与指定元素匹配的队列元素。

public boolean removeFirstOccurrence(Object o) {
        if (o == null) return false;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            // 从队首开始遍历
            for (Node<E> p = first; p != null; p = p.next) {
                // 使用equals匹配
                if (o.equals(p.item)) {
                    unlink(p);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

*  **removeLastOccurrence**

从队尾遍历，移出第一个与指定元素匹配的队列元素。

public boolean removeLastOccurrence(Object o) {
        if (o == null) return false;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            for (Node<E> p = last; p != null; p = p.prev) {
                if (o.equals(p.item)) {
                    unlink(p);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

*  **remove**

等价于removeFirstOccurrence。

public boolean remove(Object o) {
        return removeFirstOccurrence(o);
    }

*  **contains**

查看队列中是否存在指定的元素。

public boolean contains(Object o) {
        if (o == null) return false;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            for (Node<E> p = first; p != null; p = p.next)
                if (o.equals(p.item))
                    return true;
            return false;
        } finally {
            lock.unlock();
        }
    }

*  **size**

获取队列中元素的个数。

public int size() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return count;
        } finally {
            lock.unlock();
        }
    }

[JUC_BlockingDeque]: https://blog.csdn.net/weixin_50518271/article/details/119190379?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70]: /images/20220829/e186342b8c1b4e24bedd7fc45274cf44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/a404168aea9b4bfe97c3ca7e48ac8f64.png
[20210728215544724.png]: /images/20220829/ead12d1b536440759b28019fad051618.png
[20210728220009933.png]: /images/20220829/7a12b3be764f4f099138c0ef28de6d79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/4170ea16c352402593e882421be4bc33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/4ce64b402f6e41968fd21602bbdae482.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 4]: /images/20220829/2d986dcc42d1459a9c2c89db631ea1ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 5]: /images/20220829/376c49e81e614344afd61fda8d3a3295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 6]: /images/20220829/0d702a5f5f734a878c52be421a60a5f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 7]: /images/20220829/011e7906dcb24b4a85d21d66b31e4895.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 8]: /images/20220829/70b6cc72d2fb4f1094da023be538fdc3.png