开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> BlockingDeque之LinkedBlockingDeque -> 正文阅读

[数据结构与算法]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();
    }
}