java双端队列作用（java三种队列详解）

LinkedBlockingDeque概述

LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列，支持O(1)的时间复杂度从两端插入和移除元素，如不指定边界，则为Integer.MAX_VALUE。

由一个ReentrantLock保证同步，使用conditions来实现等待通知。

类图结构及重要字段

public class LinkedBlockingDeque<E>    extends AbstractQueue<E>    implements BlockingDeque<E>, java.io.Serializable {    private static final long serialVersionUID = -387911632671998426L;    /** 双向链表节点 */    static final class Node<E> {        E item;        Node<E> prev;        Node<E> next;        Node(E x) {            item = x;        }    }    /**     * 指向第一个节点     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node<E> first;    /**     * 指向最后一个节点     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node<E> last;    /** 节点数量 */    private transient int count;    /** 队列容量 */    private final int capacity;    /** 保证同步 */    final ReentrantLock lock = new ReentrantLock();    /** take操作发生的条件 */    private final Condition notEmpty = lock.newCondition();    /** put操作发生的条件 */    private final Condition notFull = lock.newCondition();    }
linkFirst
  

	尝试将节点加入到first之前，更新first，如果插入之后超出容量，返回false。
private boolean linkFirst(Node<E> node) {        // assert lock.isHeldByCurrentThread();        if (count >= capacity)            return false;        Node<E> f = first;        node.next = f;        first = node;        if (last == null)            last = node;        else            f.prev = node;        ++count;        notEmpty.signal();        return true;    }
linkLast
  

	在last节点后加入节点node，更新last。如果插入之后超出容量，返回false。
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();// 满足notEmpty条件        return true;    }
unlinkFirst
  

	移除first节点，并返回其item值，如果队列为空，则返回full。
private E unlinkFirst() {        // assert lock.isHeldByCurrentThread();        Node<E> f = first;        if (f == null)            return null;        Node<E> n = f.next;        E item = f.item;        f.item = null;        f.next = f; // help GC        first = n;        if (n == null)            last = null;        else            n.prev = null;        --count;        notFull.signal();// 满足notFull条件        return item;    }
unlinkLast
  

	移除last节点，并返回其item值，如果队列为空，则返回full。
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(); // 满足notFull条件        return item;    }
unlink
  

	移除任意一个节点，注意这里并没有操作x本身的连接，因为它可能仍被iterator使用着。
void unlink(Node<E> x) {        // assert lock.isHeldByCurrentThread();        Node<E> p = x.prev;        Node<E> n = x.next;        // 移除的是first        if (p == null) {            unlinkFirst();        // 移除的是last        } else if (n == null) {            unlinkLast();        } else {            // 移除的是中间节点            p.next = n;            n.prev = p;            x.item = null;            // Don't mess with x's links.  They may still be in use by            // an iterator.            // 这里x的prev和next指针都没有改变，因为他们可能在被iterator使用            --count;            notFull.signal();        }    }
总结
  

	LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列，支持O(1)的时间复杂度从两端插入和移除元素，如不指定边界，则为Integer.MAX_VALUE。
  

	由一个ReentrantLock保证同步，使用conditions来实现等待通知。
  

	上面介绍的所有操作基本上就是核心方法啦，诸如putFirst、putLast、takeFirst、takeLast等方法都会调用上面的核心方法，而且实现上面也是比较简单的，就是双端链表的基本操作，不懂的可以画画图帮助理解哈。