点赞再看，养成习惯，公众号搜一搜【一角钱技术】关注更多原创技术文章。本文 GitHub org_hejianhui/JavaStudy 已收录，有我的系列文章。

前言

LinkedBlockingDeque 一个由于链表结构组成的双向阻塞队列，队列头部和尾部都可以添加和移除元素，多线程并发时，可以将锁的竞争对多降到一半。

队列创建

BlockingDeque<String> deque = new LinkedBlockingDeque<String>();

应用场景

一般多用于生产者消费者模式。

我们来看一个例子：使用了LinkedBlockingQueue来模仿生产者线程和消费者线程进行数据生产和消费。

package com.niuh.deque;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <p>
 * LinkedBlockingQueue示例，生产者消费者
 * </p>
 */
public class LinkedBlockingQueueRunner {
    public static void main(String[] args) {
        BlockingQueue<Integer> shareQueue = new LinkedBlockingDeque<>();

        Producer P = new Producer(shareQueue);
        Consumer C = new Consumer(shareQueue);

        P.start();
        C.start();
    }
}

/**
 * 生产者
 */
class Producer extends Thread {
    private BlockingQueue<Integer> sharedQueue;

    public Producer(BlockingQueue<Integer> shareQueue) {
        super("PRODUCER");
        this.sharedQueue = shareQueue;
    }

    public void run() {
        //no synchronization needed
        for (int i = 0; i < 10; i++) {
            try {
                System.out.println(getName() + " produced " + i);
                sharedQueue.put(i);
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

/**
 * 消费者
 */
class Consumer extends Thread {
    private BlockingQueue<Integer> shareQueue;

    public Consumer(BlockingQueue<Integer> shareQueue) {
        super("CONSUMER");
        this.shareQueue = shareQueue;
    }

    public void run() {
        try {
            while (true) {
                Integer item = shareQueue.take();
                System.out.println(getName() + " consumed " + item);
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

工作原理

LinkedBlockingDeque的数据结构，如下图所示：

说明：

LinkedBlockingDeque继承于AbstractQueue，它本质上是一个支持FIFO和FILO的双向的队列。
LinkedBlockingDeque实现了BlockingDeque接口，它支持多线程并发。当多线程竞争同一个资源时，某线程获取到该资源之后，其它线程需要阻塞等待。
LinkedBlockingDeque是通过双向链表实现的。

first是双向链表的表头。
last是双向链表的表尾。
count是LinkedBlockingDeque的实际大小，即双向链表中当前节点个数。
capacity是LinkedBlockingDeque的容量，它是在创建LinkedBlockingDeque时指定的。
lock是控制对LinkedBlockingDeque的互斥锁，当多个线程竞争同时访问LinkedBlockingDeque时，某线程获取到了互斥锁lock，其它线程则需要阻塞等待，直到该线程释放lock，其它线程才有机会获取lock从而获取cpu执行权。
notEmpty和notFull分别是“非空条件”和“未满条件”。通过它们能够更加细腻进行并发控制。

-- 若某线程(线程A)要取出数据时，队列正好为空，则该线程会执行notEmpty.await()进行等待；当其它某个线程(线程B)向队列中插入了数据之后，会调用notEmpty.signal()唤醒“notEmpty上的等待线程”。此时，线程A会被唤醒从而得以继续运行。此外，线程A在执行取操作前，会获取takeLock，在取操作执行完毕再释放takeLock。

-- 若某线程(线程H)要插入数据时，队列已满，则该线程会它执行notFull.await()进行等待；当其它某个线程(线程I)取出数据之后，会调用notFull.signal()唤醒“notFull上的等待线程”。此时，线程H就会被唤醒从而得以继续运行。此外，线程H在执行插入操作前，会获取putLock，在插入操作执行完毕才释放putLock。

源码分析

定义

LinkedBlockingDeque的类继承关系如下：

其包含的方法定义如下：

BlockingDeque接口

BlockingDeque 继承 BlockingQueue 和 Deque 两个接口，其类继承关系图如下：

其主要的方法如下：

接口名	说明
void addFirst(E e)	添加元素到头部。如果没有多余的空间。则扔出异常。
void addLast(E e)	添加元素到尾部。如果没有多余的空间。则抛出异常。
boolean offerFirst(E e)	添加元素到头部。如果没有多余的空间。则返回false
boolean offerLast(E e)	添加元素到尾部。如果没有多余的空间。则返回false
void putFirst(E e)	添加元素到头部。如果没有多余的空间。则进行等待
void putLast(E e)	添加元素到尾部。如果没有多余的空间。则进行等待
boolean offerFirst(E e, long timeout, TimeUnit unit)	添加元素到头部。如果没有多余的空间。则进行等待。具有超时机制
boolean offerLast(E e, long timeout, TimeUnit unit)	添加元素到尾部。如果没有多余的空间。则进行等待。具有超时机制
E takeFirst()	查询并移除头部元素。如果没有多余的空间。则进行等待。
E takeLast()	查询并移除尾部元素。如果没有多余的空间。则进行等待。

成员属性

从下面可以得到LinkedBlockingDeque内部只有一把锁以及该锁上关联的两个条件，所以可以推断同一时刻只有一个线程可以在队头或者队尾执行入队或出队操作。可以发现这点和LinkedBlockingQueue不同，LinkedBlockingQueue可以同时有两个线程在两端执行操作。

// 队列的头节点
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();

内部类Node

一个Node对象代表一个链表节点，其属性item表示当前节点保存的元素(item为null时表示当前节点已经被删除)，next属性表示当前节点的后继节点，prev属性表示当前节点的前驱节点。

static final class Node<E> {
    // 节点数据
    E item;
    // 上一个节点
    Node<E> prev;
    // 下一个节点
    Node<E> next;
    Node(E x) {
        item = x;
    }
}

构造函数

提供了三个构造方法，LinkedBlockingDeque(int)是其主要的构造方法，构造方法主要涉及对队列容量的初始化。在使用无参构造方法时，阻塞队列的容量是Integer.MAX_VALUE，即无限大。

在初始化后，队列中不含任何元素时，头节点、尾节点均是null。看到这三个构造方法的结构和LinkedBlockingQueue是相同的。但是LinkedBlockingQueue是存在一个哨兵节点维持头节点的，而LinkedBlockingDeque中是没有的。

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

添加元素

在队尾添加元素

put offer add offer 等方法都是在队列的尾部添加元素。它们将核心实现委托给 putLast 、offerLast 、add``Last实现

public void put(E e) throws InterruptedException {
    putLast(e);
}
public boolean offer(E e) {
    return offerLast(e);
}
public boolean add(E e) {
    addLast(e);
    return true;
}
public boolean  offer(E e, long timeout, TimeUnit unit)
    throws InterruptedException {
    return offerLast(e, timeout, unit);
}

putLast(E e)

putLast 在队尾添加元素

putLast先获取lock锁(lock.lock())，然后尝试在队尾添加一个新节点(linkLast(node))，若链接新节点失败，则(notFull.await())休眠等待直到等到”未满“通知。

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

linkLast 尝试在队列的尾部添加一个新节点。主要逻辑：

若队列已满，直接返回false(不能链接新节点) ;
将待入队节点node作为新的尾节点添加在队尾(last = node)并更新相关链接关系;
元素计数加1(++count) ;
唤醒一个等待"非空"条件的线程（notEmpty.signal()），最后返回true.

private boolean linkLast(Node<E> node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity)//队列已满，不能链接新节点
        return false;
    Node<E> l = last;
    node.prev = l;//设置node的前驱节点，它的前驱为原尾节点
    last = node;//新尾节点是刚添加的节点node
    //更新原尾节点l的后继节点
    if (first == null) //队列中没有任何节点，last first均未初始化，
       //队列中只有一个节点(元素)时，头节点first 和尾节点last指定同一节点node 
        first = node;
    else
        l.next = node;//原尾节点l的后继节点是新尾节点（刚添加的节点node）
    ++count;//元素个数加1
    notEmpty.signal();//通知一个等待"非空"条件的线程
    return true;
}

offerLast(E e)

offerLast方法与putLast类似，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();
    }
}

offerLast(e, timeout, unit)

多参数的offerLast方法，它可以看作putLast的超时版本。

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)//在超时之后没能入队，返回false
                return false;
            nanos = notFull.awaitNanos(nanos);//超时等待
        }
        return true;
    } finally {
        lock.unlock();
    }
}

addLast(E e)

addLast 在队尾添加元素，若队列已满抛出异常。

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

在队首添加元素

push(E e)

push 在队列的头部插入元素，调用addFirst

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

addFirst(E e)

在队列的头部插入元素，若队列已经满抛出IllegalStateException异常

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

putFirst(E e)

putLast在队列头部插入元素，若容量已满则阻塞等待

先获取lock锁(lock.lock())
然后尝试在队首添加一个新节点(linkFirst(node))
若链接新节点失败，则(notFull.await())休眠等待直到等到”未满“通知。

public void putFirst(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 (!linkFirst(node))
            notFull.await();
    } finally {
        lock.unlock();
    }
}

linkLast 尝试在队列的头部链接一个新节点。主要逻辑：

若队列已满，直接返回false(不能链接新节点) ;
将待入队节点node作为新的头节点添加在队首(first = node)并更新相关链接关系;
元素计数加1(++count) ;
通知一个等待"非空"条件的线程（notEmpty.signal()），最后返回true。

private boolean linkFirst(Node<E> node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity)
        //队列已满，不能链接新节点
        return false;
    Node<E> f = first;
    node.next = f;//设置node的后继节点，它的后继为原头节点
    first = node;////新的尾节点是刚添加的节点node
    //更新原头节点f的前驱节点
    if (last == null)//队列中没有任何节点，last first均未初始化
         //队列中只有一个节点(元素)时，头节点first 和尾节点last指定同一节点node
        last = node;
    else
        f.prev = node;//原头节点f的前驱节点是新头节点（刚添加的节点node）
    ++count;//元素个数加1
    notEmpty.signal();//通知一个等待"非空"条件的线程
    return true;
}

offerFirst(E e)

offerFirst方法与putFirst类似，但offerFirst在检测到队列已满时会直接返回false,不会阻塞等待。

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

offerFirst(E e, long timeout, TimeUnit unit)

多参数的offerFirst方法，它可以看作putFirst的超时版本.

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

删除元素

在队首删除元素

remove pop poll take 等方法都是在队列的尾部添加元素。它们将核心实现委托给 removeFirst 、pollFirst 、takeFirst等实现

public E take() throws InterruptedException {
    return takeFirst();
}
public E poll() {
    return pollFirst();
}
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
  return pollFirst(timeout, unit);
}
public E remove() {
    return removeFirst();
}
public E pop() {
    return removeFirst();
}

takeFirst()

takeLast先获取lock锁(lock.lock());
然后尝试在队尾取消一个节点的链接(unlinkLast());
若取消链接失败(队列已空)，则(notEmpty.await())休眠等待直到等到”非空“通知。

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

unlinkLast()尝试取消尾节点在链表中的链接

若队列为空，直接返回null(不能取消链接) ;
将原尾节点的前驱节点(Node<E> p = l.prev)作为新尾节点(last = p)并更新相关链接关系;
元素计数自减1(--count) ;
唤醒一个等待"未满"条件的线程（notFull.signal()），最后返回原尾节点中的元素(E item = l.item)。

private E unlinkLast() {
    // assert lock.isHeldByCurrentThread();
    Node<E> l = last;
    if (l == null)
         //链表未初始化，队列中没有任何元素，返回null
        return null;
    Node<E> p = l.prev;
    E item = l.item;//保存尾节点的item，最终需要返回尾节点的item
    l.item = null;//然后将原尾节点的item属性清空
    //prevn属性自指，在使用迭代器时能标识此节点已被删除
    l.prev = l; // help GC 
    last = p;//新尾节点是原尾节点的前驱继节点
     //设置新尾节点的后继节点
    if (p == null)//删除尾节点前 链表中只有一个节点l
         //将头节点first、尾节点tail都设为null，链表中没有任何节点了
        first = null;
    else//删除尾节点前链表中至少有两个节点(元素)
        p.next = null;//将新尾节点的next设为null(尾节点没有后继节点)
    --count;//元素个数减1
    notFull.signal();//唤醒一个等待”未满“条件的线程
    return item;
}

pollLast()

pollLast方法与takeLast类似，但pollLast在检测到队列为空时会直接返回null,不会阻塞等待。

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

pollLast(long timeout, TimeUnit unit)

可以看作是超时版本的takeLast，在超时之前无法出队就返回null.

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

removeLast()

removeLast`直接委托pollLast实现，若队列为空，则抛出异常NoSuchElementException。

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

删除指定的元素

remove、 removeFirstOccurrence方法均是从队列头部开始向后查找，在给定元素第一次出现的位置上将之删除。
removeLastOccurrence是从队列尾部开始向前查找，在给定元素第一次出现的位置上将之删除。

remove(Object o)

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

removeFirstOccurrence(Object o)

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) {//从队列头部开始向后查找
            if (o.equals(p.item)) {
                unlink(p);//取消此节点在链表中的链接关系
                return true;
            }
        }
        return false;
    } finally {
        lock.unlock();
    }
}

removeLastOccurrence(Object o)

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

unlink() 将一个节点从链表中删除

void unlink(Node<E> x) {
    // assert lock.isHeldByCurrentThread();
    Node<E> p = x.prev;
    Node<E> n = x.next;
    if (p == null) {
        //如果待删除节点是头节点，
        unlinkFirst();
    } else if (n == null) {
        //如果待删除节点是尾节点
        unlinkLast();
    } else {//待删除节点是非头尾的中间节点
        //通过next 、prev属性，将删除节点的前驱节点p和待删除节点的后继节点n直接链接在一起，待删除节点x已被排除在链表外
        p.next = n;//待删除节点的前驱节点的next属性设为 待删除节点的后继节点
        n.prev = p;//待删除节点的后继节点的prev属性设为 待删除节点的前驱节点
        x.item = null;//清空item
        // Don't mess with x's links.  They may still be in use by
        // an iterator.
        --count;
        notFull.signal();
    }
}

获取队列首尾元素

获取队首元素

element、 getFirst返回队列的首元素但不删除，若队列为空则抛出异常NoSuchElementException。
peek 、peekFirst返回队列的首元素但不删除，若队列为空则返回null.

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

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

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

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

获取队尾元素

getLast返回队列的尾元素但不删除，若队列为空则抛出异常NoSuchElementException。
peekLast返回队列的尾元素但不删除，若队列为空则返回null

public E getLast() {
    E x = peekLast();
    if (x == null) throw new NoSuchElementException();
    return x;
}
public E peekLast() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return (last == null) ? null : last.item;
    } finally {
        lock.unlock();
    }
 }

其他方法

contains(Object 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()

size方法返回队列中元素的个数

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

clear()

clear清空队列中的所有元素。其主要逻辑：

从头到尾清空所有的链接关系(f.prev = null;f.next = null;);
将头尾节点同时设空(first = last = null);
元素个数计数设为0(count = 0)；
唤醒所有等待“未满”条件的线程(notFull.signalAll())。

public void clear() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        for (Node<E> f = first; f != null; ) {
            f.item = null;
            Node<E> n = f.next;
            f.prev = null;
            f.next = null;
            f = n;
        }
        first = last = null;
        count = 0;
        notFull.signalAll();
    } finally {
        lock.unlock();
    }
}

迭代器

AbstractItr

AbstractItr是实现Iterator接口的一个抽象类，它为迭代器提供了很多默认实现，它是前序遍历迭代器Itr和后序遍历迭代器DescendingItr的父类。**

成员变量

Node<E> next; // 下次迭代的节点
E nextItem; // next()方法返回的元素
private Node<E> lastRet; // 上次迭代的节点

构造方法

构造方法将初始化next和nextItem属性

AbstractItr() {
    // set to initial position
    final ReentrantLock lock = LinkedBlockingDeque.this.lock;
    lock.lock();
    try {
        next = firstNode();
        nextItem = (next == null) ? null : next.item;
    } finally {
        lock.unlock();
    }
}

抽象方法

抽象方法firstNode 、nextNode分别返回迭代器遍历的第一个节点、下一个节点

abstract Node<E> firstNode();
abstract Node<E> nextNode(Node<E> n);

hasNext()

hasNext() 根据next属性是否为空判定后面是否还有元素

public boolean hasNext() {
    return next != null;
}

next()

next() 返回下一个元素

public E next() {
    if (next == null)
        throw new NoSuchElementException();
    lastRet = next; //将next作为上次迭代的节点
    E x = nextItem;
    advance(); //更新next 和nextItem属性
    return x;
}

advance()

advance() 方法用于更新next 和nextItem属性

void advance() {
    final ReentrantLock lock = LinkedBlockingDeque.this.lock;
    lock.lock();
    try {
        // assert next != null;
        next = succ(next);
        nextItem = (next == null) ? null : next.item;
    } finally {
        lock.unlock();
    }
}

succ()

succ返回指定节点的后继节点

private Node<E> succ(Node<E> n) {
    // Chains of deleted nodes ending in null or self-links
    // are possible if multiple interior nodes are removed.
    for (;;) {
        Node<E> s = nextNode(n); //nextNode是AbstractItr的抽象方法，需要子类实现，  它返回下个节点
        if (s == null)  
            //n是尾节点，所以s没有后继节点，返回null
            return null;
        else if (s.item != null)
            //n是非尾节点，所以其后继节点s的item不为空 ,返回s
            return s;
        else if (s == n)
            //s.item==null 且 n.next==n 
            //item为空、next属性自指，表示原头(尾)节点n逻辑上已被删除，first(last)更新延迟
            //获取最新的first(last)
            return firstNode();
        else 
            //s.item==null && n.next!=n 
            //item为空但next属性不自指 ，表示节点s在链表(非头尾)中间位置,在逻辑s上已被删除，
            //（可能是remove(Object)方法在队列中部删除了元素）需要继续向下查找有效节点
            n = s;
    }
}

remove()

remove方法移除当前迭代的元素，此方法与外部类的remove方法类似。

public void remove() {
    Node<E> n = lastRet;
    if (n == null)
        throw new IllegalStateException();
    lastRet = null;//将lastRet设为null,可指示这个元素节点被删除
    final ReentrantLock lock = LinkedBlockingDeque.this.lock;
    lock.lock();
    try {
        if (n.item != null)
            unlink(n);//外部类的方法，将n节点从链表中删除
    } finally {
        lock.unlock();
    }
}

Itr与DescendingItr

Itr和 DescendingItr都实现了类型的抽象方法firstNode 、nextNode。Itr代表前序迭代器，从头节点开始向后遍历，firstNode方法返回头节点，nextNode返回指定节点的后继节点。而DescendingItr代表后序迭代器，从尾节点开始向前遍历，firstNode方法返回尾节点，nextNode返回指定节点的前驱节点

/** Forward iterator */
private class Itr extends AbstractItr {
    Node<E> firstNode() { return first; }
    Node<E> nextNode(Node<E> n) { return n.next; }
}

/** Descending iterator */
private class DescendingItr extends AbstractItr {
    Node<E> firstNode() { return last; }
    Node<E> nextNode(Node<E> n) { return n.prev; }
}

示例Demo

package com.niuh.deque;

import java.util.Iterator;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <p>
 * LinkedBlockingDeque示例
 * </p>
 */
public class LinkedBlockingDequeDemo {
    
    public static void main(String[] args) {
        /**
         * 1.1、LinkedBlockingDeque():
         *           创建一个容量为 Integer.MAX_VALUE 的 LinkedBlockingDeque。
         * 1.2、LinkedBlockingDeque(int capacity):
         *           创建一个具有给定（固定）容量的 LinkedBlockingDeque。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque = new LinkedBlockingDeque<>();
        /**
         * 1、add(E e):在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾，返回值为Boolean。
         */
        Boolean addBoolean = linkedBlockingDeque.add(5);
        System.out.println("是否添加成功：" + addBoolean);


        /**
         *  2、addFirst(E e)：如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的开头；
         *                   如果当前没有空间可用，则抛出 IllegalStateException。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque1 = new LinkedBlockingDeque<>();
        linkedBlockingDeque1.addFirst(1);
        linkedBlockingDeque1.addFirst(2);
        linkedBlockingDeque1.addFirst(3);


        /**
         * 3、iterator()：返回在此双端队列元素上以恰当顺序进行迭代的迭代器。
         */
        Iterator<Integer> iterator = linkedBlockingDeque1.iterator();
        while (iterator.hasNext()) {
            System.out.println("Iterator的addFirst结果：" + iterator.next());
        }


        /**
         * 4、addLast(E e) ：如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的末尾；
         *                   如果当前没有空间可用，则抛出 IllegalStateException
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque2 = new LinkedBlockingDeque<>();
        linkedBlockingDeque2.addLast(1);
        linkedBlockingDeque2.addLast(2);
        linkedBlockingDeque2.addLast(3);
        Iterator<Integer> iterator1 = linkedBlockingDeque2.iterator();
        while (iterator1.hasNext()) {
            System.out.println("Iterator的addLast结果：" + iterator1.next());
        }


        /**
         * 5、clear()：以原子方式 (atomically) 从此双端队列移除所有元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque3 = new LinkedBlockingDeque<>();
        linkedBlockingDeque3.add(1);
        linkedBlockingDeque3.add(2);
        linkedBlockingDeque3.add(3);
        linkedBlockingDeque3.clear();
        System.out.println("================");
        Iterator<Integer> iterator2 = linkedBlockingDeque3.iterator();
        while (iterator2.hasNext()) {
            System.out.println("Iterator的clear结果：" + iterator2.next());
        }
        System.out.println("================");

        /**
         * 6、contains(Object o) ：如果此双端队列包含指定的元素，则返回 true
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque4 = new LinkedBlockingDeque<>();
        linkedBlockingDeque4.add(1);
        linkedBlockingDeque4.add(2);
        linkedBlockingDeque4.add(3);
        Boolean contains3Boolean = linkedBlockingDeque4.contains(3);
        Boolean contains4Boolean = linkedBlockingDeque4.contains(4);
        System.out.println("是否包含3：" + contains3Boolean + " 是否包含4：" + contains4Boolean);

        /**
         * 7、element()：获取但不移除此双端队列表示的队列的头部
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque5 = new LinkedBlockingDeque<>();
        linkedBlockingDeque5.add(1);
        linkedBlockingDeque5.add(2);
        linkedBlockingDeque5.add(3);
        Integer elementResult = linkedBlockingDeque5.element();
        System.out.println("队列的头部: " + elementResult);

        /**
         * 8、getFirst() ：获取，但不移除此双端队列的第一个元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque6 = new LinkedBlockingDeque<>();
        linkedBlockingDeque6.add(1);
        linkedBlockingDeque6.add(2);
        linkedBlockingDeque6.add(3);
        Integer firstResult = linkedBlockingDeque6.getFirst();
        System.out.println("双端队列的第一个元素: " + firstResult);


        /**
         * 9、   getLast() :获取，但不移除此双端队列的最后一个元素
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque7 = new LinkedBlockingDeque<>();
        linkedBlockingDeque7.add(3);
        linkedBlockingDeque7.add(4);
        linkedBlockingDeque7.add(5);
        Integer lastResult = linkedBlockingDeque7.getLast();
        System.out.println("双端队列的最后一个元素: " + lastResult);


        /**
         * 10.1、offer(E e) :如果立即可行且不违反容量限制，
         *                  则将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），
         *                  并在成功时返回 true；如果当前没有空间可用，则返回 false
         *
         * 10.2、offer(E e, long timeout, TimeUnit unit) :
         *                  将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），
         *                  必要时将在指定的等待时间内一直等待可用空间,返回值为Boolean。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque8 = new LinkedBlockingDeque<>();
        linkedBlockingDeque8.offer(1);
        linkedBlockingDeque8.offer(2);
        linkedBlockingDeque8.offer(3);
        Iterator<Integer> iterator3 = linkedBlockingDeque8.iterator();
        while (iterator3.hasNext()) {
            System.out.println("Iterator的offer结果：" + iterator3.next());
        }


        /**
         * 11.1、offerFirst(E e) ：
         *           如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的开头，
         *           并在成功时返回 true；如果当前没有空间可用，则返回 false。
         * 11.2、fferFirst(E e, long timeout, TimeUnit unit)：
         *           将指定的元素插入此双端队列的开头，必要时将在指定的等待时间内等待可用空间。
         *           返回值为Boolean。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque9 = new LinkedBlockingDeque<>();
        linkedBlockingDeque9.offerFirst(1);
        linkedBlockingDeque9.offerFirst(2);
        linkedBlockingDeque9.offerFirst(3);
        Iterator<Integer> iterator4 = linkedBlockingDeque9.iterator();
        while (iterator4.hasNext()) {
            System.out.println("Iterator的offerFirst结果：" + iterator4.next());
        }


        /**
         * 12.1、offerLast(E e):
         *           如果立即可行且不违反容量限制，则将指定的元素插入此双端队列的末尾，并在成功时返回 true；如果当前没有空间可用，则返回 false。
         * 12.2、offerLast(E e, long timeout, TimeUnit unit):
         *           将指定的元素插入此双端队列的末尾，必要时将在指定的等待时间内等待可用空间。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque10 = new LinkedBlockingDeque<>();
        linkedBlockingDeque10.offerLast(1);
        linkedBlockingDeque10.offerLast(2);
        linkedBlockingDeque10.offerLast(3);
        Iterator<Integer> iterator5 = linkedBlockingDeque10.iterator();
        while (iterator5.hasNext()) {
            System.out.println("Iterator的offerLast结果：" + iterator5.next());
        }


        /**
         * 13、peek():获取但不移除此双端队列表示的队列的头部（即此双端队列的第一个元素）；
         *            如果此双端队列为空，则返回 null
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque11 = new LinkedBlockingDeque<>();
        linkedBlockingDeque11.add(1);
        linkedBlockingDeque11.add(2);
        linkedBlockingDeque11.add(3);
        Integer peekResult = linkedBlockingDeque11.peek();
        System.out.println("peekResult的结果：" + peekResult);

        /**
         * 14、peekFirst():获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque12 = new LinkedBlockingDeque<>();
        linkedBlockingDeque12.add(3);
        linkedBlockingDeque12.add(4);
        linkedBlockingDeque12.add(5);
        Integer peekFirstResult = linkedBlockingDeque12.peekFirst();
        System.out.println("peekFirstResult的结果：" + peekFirstResult);


        /**
         * 15、peekLast() ：获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque13 = new LinkedBlockingDeque<>();
        linkedBlockingDeque13.add(6);
        linkedBlockingDeque13.add(7);
        linkedBlockingDeque13.add(8);
        Integer peekLastResult = linkedBlockingDeque13.peekLast();
        System.out.println("peekLastResult的结果：" + peekLastResult);

        /**
         * 16.1、poll() :获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素）；
         *            如果此双端队列为空，则返回 null。
         * 16.2、poll(long timeout, TimeUnit unit)：
         *           获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素），
         *           如有必要将在指定的等待时间内等待可用元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque14 = new LinkedBlockingDeque<>();
        linkedBlockingDeque14.add(9);
        linkedBlockingDeque14.add(10);
        linkedBlockingDeque14.add(11);
        Integer pollResult = linkedBlockingDeque14.poll();
        System.out.println("peekLastResult的结果：" + pollResult);
        System.out.println("linkedBlockingDeque14是否还包含9：" + linkedBlockingDeque14.contains(9));


        /**
         * 17.1、pollFirst() ：
         *           获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
         * 17.2、pollFirst(long timeout, TimeUnit unit) :
         *           获取并移除此双端队列的第一个元素，必要时将在指定的等待时间等待可用元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque15 = new LinkedBlockingDeque<>();
        linkedBlockingDeque15.addFirst(9);
        linkedBlockingDeque15.addFirst(10);
        linkedBlockingDeque15.addFirst(11);
        Integer pollFirstResult = linkedBlockingDeque15.pollFirst();
        System.out.println("pollFirstResult的结果：" + pollFirstResult);
        System.out.println("linkedBlockingDeque15是否还包含11：" + linkedBlockingDeque15.contains(11));

        /**
         * 18.1、pollLast()
         *           获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
         * 18.2、pollLast(long timeout, TimeUnit unit)
         *           获取并移除此双端队列的最后一个元素，必要时将在指定的等待时间内等待可用元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque16 = new LinkedBlockingDeque<>();
        linkedBlockingDeque16.add(9);
        linkedBlockingDeque16.add(10);
        linkedBlockingDeque16.add(11);
        Integer pollLastResult = linkedBlockingDeque16.pollLast();
        System.out.println("pollLastResult的结果：" + pollLastResult);
        System.out.println("linkedBlockingDeque16是否还包含11：" + linkedBlockingDeque16.contains(11));

        /**
         * 19、  pop() :从此双端队列所表示的堆栈中弹出一个元素（移除效果）
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque17 = new LinkedBlockingDeque<>();
        linkedBlockingDeque17.addFirst(1);
        linkedBlockingDeque17.addFirst(2);
        linkedBlockingDeque17.addFirst(3);
        Integer pop1Result = linkedBlockingDeque17.pop();
        System.out.println("pop2Result的结果：" + pop1Result);
        Integer pop2Result = linkedBlockingDeque17.pop();
        System.out.println("pop2Result的结果：" + pop2Result);
        System.out.println("linkedBlockingDeque17是否还包含2：" + linkedBlockingDeque17.contains(2));

        /**
         * 20、push(E e) ：将元素推入此双端队列表示的栈。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque18 = new LinkedBlockingDeque<>();
        linkedBlockingDeque18.push(1);
        linkedBlockingDeque18.push(2);
        linkedBlockingDeque18.push(3);
        Iterator<Integer> iterator6 = linkedBlockingDeque18.iterator();
        while (iterator6.hasNext()) {
            System.out.println("Iterator的push结果：" + iterator6.next());
        }

        /**
         * 21、put(E e) :将指定的元素插入此双端队列表示的队列中（即此双端队列的尾部），
         *               必要时将一直等待可用空间。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque19 = new LinkedBlockingDeque<>();
        try {
            linkedBlockingDeque19.put(1);
            linkedBlockingDeque19.put(2);
            linkedBlockingDeque19.put(3);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        Iterator<Integer> iterator7 = linkedBlockingDeque19.iterator();
        while (iterator7.hasNext()) {
            System.out.println("Iterator的put结果：" + iterator7.next());
        }

        /**
         * 22、putFirst(E e) :将指定的元素插入此双端队列的开头，必要时将一直等待可用空间。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque20 = new LinkedBlockingDeque<>();
        try {
            linkedBlockingDeque20.putFirst(1);
            linkedBlockingDeque20.putFirst(2);
            linkedBlockingDeque20.putFirst(3);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        Iterator<Integer> iterator8 = linkedBlockingDeque20.iterator();
        while (iterator8.hasNext()) {
            System.out.println("Iterator的putFirst结果：" + iterator8.next());
        }

        /**
         * 23、putLast(E e) :将指定的元素插入此双端队列的末尾，必要时将一直等待可用空间。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque21 = new LinkedBlockingDeque<>();
        try {
            linkedBlockingDeque21.putLast(1);
            linkedBlockingDeque21.putLast(2);
            linkedBlockingDeque21.putLast(3);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        Iterator<Integer> iterator9 = linkedBlockingDeque21.iterator();
        while (iterator9.hasNext()) {
            System.out.println("Iterator的putLast结果：" + iterator9.next());
        }


        /**
         * 24、remove():获取并移除此双端队列表示的队列的头部。返回一个E
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque22 = new LinkedBlockingDeque<>();
        linkedBlockingDeque22.addFirst(1);
        linkedBlockingDeque22.addFirst(2);
        linkedBlockingDeque22.addFirst(3);
        Integer removeResult = linkedBlockingDeque22.remove();
        System.out.println("removeResult的结果：" + removeResult);
        System.out.println("linkedBlockingDeque22是否还包含3：" + linkedBlockingDeque22.contains(3));


        /**
         * 25、remove(Object o) :从此双端队列移除第一次出现的指定元素,返回值为Boolean。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque23 = new LinkedBlockingDeque<>();
        linkedBlockingDeque23.addFirst(1);
        linkedBlockingDeque23.addFirst(2);
        linkedBlockingDeque23.addFirst(3);
        Boolean removeBoolean = linkedBlockingDeque23.remove(3);
        System.out.println("是否remove了3 ：" + removeBoolean);

        /**
         * 26、removeFirst():获取并移除此双端队列第一个元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque24 = new LinkedBlockingDeque<>();
        linkedBlockingDeque24.addLast(1);
        linkedBlockingDeque24.addLast(2);
        linkedBlockingDeque24.addLast(3);
        Integer removeFirstResult = linkedBlockingDeque24.removeFirst();
        System.out.println("removeFirstResult：" + removeFirstResult);
        System.out.println("linkedBlockingDeque24是否还包含1：" + linkedBlockingDeque24.contains(1));


        /**
         * 27、  removeLast():获取并移除此双端队列的最后一个元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque25 = new LinkedBlockingDeque<>();
        linkedBlockingDeque25.addLast(4);
        linkedBlockingDeque25.addLast(5);
        linkedBlockingDeque25.addLast(6);
        Integer removeLastResult = linkedBlockingDeque25.removeLast();
        System.out.println("removeLastResult：" + removeLastResult);
        System.out.println("linkedBlockingDeque25是否还包含6：" + linkedBlockingDeque25.contains(6));


        /**
         * 28、take():获取并移除此双端队列表示的队列的头部（即此双端队列的第一个元素），
         *           必要时将一直等待可用元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque26 = new LinkedBlockingDeque<>();
        linkedBlockingDeque26.push(4);
        linkedBlockingDeque26.push(5);
        linkedBlockingDeque26.push(6);
        Integer takeResult = null;
        try {
            takeResult = linkedBlockingDeque26.take();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("takeResult：" + takeResult);
        System.out.println("linkedBlockingDeque26是否还包含6：" + linkedBlockingDeque26.contains(6));

        /**
         * 29、takeFirst() :获取并移除此双端队列的第一个元素，必要时将一直等待可用元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque27 = new LinkedBlockingDeque<>();
        linkedBlockingDeque27.push(7);
        linkedBlockingDeque27.push(8);
        linkedBlockingDeque27.push(9);
        Integer takeFirstResult = null;
        try {
            takeFirstResult = linkedBlockingDeque27.takeFirst();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("takeFirst：" + takeFirstResult);
        System.out.println("linkedBlockingDeque27是否还包含9：" + linkedBlockingDeque27.contains(9));


        /**
         * 30、takeLast():获取并移除此双端队列的最后一个元素，必要时将一直等待可用元素。
         */
        LinkedBlockingDeque<Integer> linkedBlockingDeque28 = new LinkedBlockingDeque<>();
        linkedBlockingDeque28.push(10);
        linkedBlockingDeque28.push(11);
        linkedBlockingDeque28.push(12);
        Integer takeLastResult = null;
        try {
            takeLastResult = linkedBlockingDeque28.takeLast();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("takeLastResult：" + takeLastResult);
        System.out.println("linkedBlockingDeque28是否还包含10：" + linkedBlockingDeque28.contains(10));


    }
}

总结

LinkedBlockingDeque 内部的数据结构是一个双向链表，在头尾位置它均能插入、删除节点（元素），同时因为每个节点都要保存前驱、后继节点的引用，它能够（前序、后序）双向遍历链表。也因为在其头、尾位置均能出队，它可用在工作窃取算法中；
LinkedBlockingDeque 在构造方法初始化后，头尾节点均为 null，未初始化；而 LinkedBlockingQueue 在构造方法初始化后，头尾节点会被初始化，它们指向同一个节点（item 为 null）；
LinkedBlockingDeque 的头节点first会保存元素，first.item 永不为空；而 LinkedBlockingQueue 的头节点first 不保存元素，first.item 一直为空，头节点的后继节点 first.next 才是链表中保存首元素的节点。
和LinkedBlockingQueue一样，LinkedBlockingDeque 在原头（尾）出队后利用 next（prev）属性自指标识此节点在逻辑上已被删除；

LinkedBlockingDeque与LinkedList区别

package com.niuh.deque;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingDeque;

/*
 *   LinkedBlockingDeque是“线程安全”的队列，而LinkedList是非线程安全的。
 *
 *   下面是“多个线程同时操作并且遍历queue”的示例
 *   (1) 当queue是LinkedBlockingDeque对象时，程序能正常运行。
 *   (2) 当queue是LinkedList对象时，程序会产生ConcurrentModificationException异常。
 *
 */
public class LinkedBlockingDequeRunner {

    // TODO: queue是LinkedList对象时，程序会出错。
    // private static Queue<String> queue = new LinkedList<String>();
    private static Queue<String> queue = new LinkedBlockingDeque<String>();

    public static void main(String[] args) {

        // 同时启动两个线程对queue进行操作！
        new MyThread("A").start();
        new MyThread("B").start();
    }

    private static void printAll() {
        String value;
        Iterator iter = queue.iterator();
        while (iter.hasNext()) {
            value = (String) iter.next();
            System.out.print(value + ", ");
        }
        System.out.println();
    }

    private static class MyThread extends Thread {
        MyThread(String name) {
            super(name);
        }

        @Override
        public void run() {
            int i = 0;
            while (i++ < 6) {
                // “线程名” + "-" + "序号"
                String val = Thread.currentThread().getName() + i;
                queue.add(val);
                // 通过“Iterator”遍历queue。
                printAll();
            }
        }
    }
}

输出结果：

A1, 
A1, A2, 
A1, A2, A3, 
A1, A2, A3, A4, 
A1, A2, A3, A4, A5, 
A1, A2, A3, A4, A5, A6, 
A1, A2, A3, A4, A5, A6, B1, 
A1, A2, A3, A4, A5, A6, B1, B2, 
A1, A2, A3, A4, A5, A6, B1, B2, B3, 
A1, A2, A3, A4, A5, A6, B1, B2, B3, B4, 
A1, A2, A3, A4, A5, A6, B1, B2, B3, B4, B5, 
A1, A2, A3, A4, A5, A6, B1, B2, B3, B4, B5, B6,

结果说明：示例程序中，启动两个线程(线程A和线程B)分别对LinkedBlockingDeque进行操作:

以线程A而言，它会先获取“线程名”+“序号”，然后将该字符串添加到LinkedBlockingDeque中；

接着，遍历并输出LinkedBlockingDeque中的全部元素。

线程B的操作和线程A一样，只不过线程B的名字和线程A的名字不同。

当queue是LinkedBlockingDeque对象时，程序能正常运行。

如果将queue改为LinkedList时，程序会产生ConcurrentModificationException异常。

PS：以上代码提交在 Github ：https://github.com/Niuh-Study/niuh-juc-final.git

PS：这里有一个技术交流群（QQ群:1158819530），方便大家一起交流，持续学习，共同进步，有需要的可以加一下。

文章持续更新，可以公众号搜一搜「一角钱技术」第一时间阅读，本文 GitHub org_hejianhui/JavaStudy 已经收录，欢迎 Star。

阻塞队列 — LinkedBlockingDeque源码分析

前言