[数据结构与算法]BlockingDeque之LinkedBlockingDeque

关键词：BlockingDeque? ??LinkedBlockingDeque? ??Deque?

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

█?LinkedBlockingDeque

字段：

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;
    }
}

• 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双端队列》）

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;

②node.next = f;

③first = node;

④last = node;

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

①Node<E> f = first;

②node.next = f;

③first = node;

④f.prev = node

• 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();
    }
}