java.util.concurrent 之BlockingDeque

港控/mmm° 2022-07-16 12:07 120阅读 0赞

### BlockingDeque ###

[Java][].util.concruuent包中的BlockingDeque接口是一种双端队列，向其中加入元素或从中取出元素都是线程安全的。这里展示如何使用BlockingDeque。

BlockingDeque是一个双端队列，如果完全不可能对双端队列进行插入或者删除元素，它将会阻塞线程。

deque 是 “Double Ended Queue”的简称。因此一个deque可以从两端插入和取出元素的。

#### BlockingDeque使用说明 ####

BlockingDeque用于一个线程对同个一个双端队列进行生产和消费元素。也常用于生产线程需要在队列两端插入元素，消费线程需要从队列两端移除元素，下面是一个图示：   
![这里写图片描述][20160706172122975]   
一个线程生产元素并将元素插入到队列的两端。如果当前队列是满的，插入线程将会被阻塞直到一个移除元素的线程从队列中取出一个元素。同样，如果队列当前是空的，移除元素的线程会被阻塞直到一个插入元素的线程向队列中插入了一个元素。

BlockingDeque的方法

对于在队列中插入、删除和检查元素操作BlockingQueue有4类不同的方法。如果操作不能立即执行，每一类方法的行为将不同。下面是方法列表：

<table style="width:946px; background-color:transparent; border-collapse:collapse; border-spacing:0px; border:1px solid rgb(238,238,238)"> 
 <thead style=""> 
  <tr style=""> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> operation</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Throws Exception</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Special Value</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Blocks</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Times Out</th> 
  </tr> 
 </thead> 
 <tbody style=""> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Insert</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> addFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> offerFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> putFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> offerFirst(o, timeout, timeunit)</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Remove</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> removeFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> pollFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> takeFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> pollFirst(timeout, timeunit)</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> Examine</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> getFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> peekFirst(o)</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> &nbsp;</td> 
  </tr> 
 </tbody> 
</table>

对于4种不同行为的说明参见BlockingQueuez中的说明。

#### BlockingDeque继承自BlockingQueue ####

BlockingDeque接口继承自BlockingQueue接口。这意味着你可以把BlockingDeque作为BlockingQueue来使用。如果你这样做，那么各种插入元素的方法将会把元素增加到队列的尾部，并且将会从队列的头部开始移除元素。

下面的列表列出了BlockingQueue方法在BlockingDeque中的实现。

<table style="width:946px; background-color:transparent; border-collapse:collapse; border-spacing:0px; border:1px solid rgb(238,238,238)"> 
 <thead style=""> 
  <tr style=""> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> BlockingDeque</th> 
   <th style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> BlockingQueue</th> 
  </tr> 
 </thead> 
 <tbody style=""> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> add()</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> addLast()</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> offer() x 2</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> offerLast() x 2</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> put()</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> putLast()</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> remove()</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> removeFirst()</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> poll() x 2</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> pollFirst()</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> take()</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> takeFirst()</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> element()</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> getFirst()</td> 
  </tr> 
  <tr style=""> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> peek()</td> 
   <td style="padding:8px; line-height:20px; vertical-align:top; border:1px solid rgb(238,238,238)"> peekFirst()</td> 
  </tr> 
 </tbody> 
</table>

#### BlockingDeque的具体实现 ####

由于BlockingDeque是一个接口类，使用时需要使用它的实现类。Java.util.concurrent包中有以下关于BlockingDeque接口的实现类:

*  LinkedBlockingDeque

### LinkedBlockingDeque ###

LinkedBlockingDeque类实现了BlockingDeque接口。   
LinkedBlockingDeque是一个双端队列，如果一个线程试图从一个空的队列中取出元素，它将被阻塞住，不管线程是从哪一端去获取元素。

public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {
        void addFirst(E e);
        void addLast(E e);  
        boolean offerFirst(E e); 
        boolean offerLast(E e); 
        void putFirst(E e) throws InterruptedException;  
        void putLast(E e) throws InterruptedException;
        boolean offerFirst(E e, long timeout, TimeUnit unit)
            throws InterruptedException;
        boolean offerLast(E e, long timeout, TimeUnit unit)
            throws InterruptedException;
        E takeFirst() throws InterruptedException; 
        E takeLast() throws InterruptedException;
        E pollFirst(long timeout, TimeUnit unit)
            throws InterruptedException;
        E pollLast(long timeout, TimeUnit unit)
            throws InterruptedException;
        boolean removeFirstOccurrence(Object o);
        boolean removeLastOccurrence(Object o);
        boolean add(E e);
        boolean offer(E e);
        void put(E e) throws InterruptedException; 
        boolean offer(E e, long timeout, TimeUnit unit)
            throws InterruptedException; 
        E remove();
        E poll();
        E take() throws InterruptedException; 
        E poll(long timeout, TimeUnit unit)
            throws InterruptedException;
        E element(); 
        E peek();
        boolean remove(Object o);
        public boolean contains(Object o);
        public int size();
        Iterator<E> iterator();
        void push(E e);
    }

package java.util.concurrent;
    
    import java.util.AbstractQueue;
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
    import java.util.concurrent.locks.Condition;
    import java.util.concurrent.locks.ReentrantLock;
    import java.util.Spliterator;
    import java.util.Spliterators;
    import java.util.function.Consumer;
    
    
    public class LinkedBlockingDeque<E>
        extends AbstractQueue<E>
        implements BlockingDeque<E>, java.io.Serializable {
    
       
        private static final long serialVersionUID = -387911632671998426L;
            E item;
            Node<E> prev;
            Node<E> next;
            Node(E x) {
                item = x;
            }
        }
        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();
        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();
            }
        }
        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;
        }
        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;
        }
        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();
            return item;
        }
        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;
        }
        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 {
                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.
                --count;
                notFull.signal();
            }
        }
        public void addFirst(E e) {
            if (!offerFirst(e))
                throw new IllegalStateException("Deque full");
        }
        public void addLast(E e) {
            if (!offerLast(e))
                throw new IllegalStateException("Deque full");
        }
        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();
            }
        }
        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();
            }
        }
        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();
            }
        }
        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();
            }
        }
        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();
            }
        }
        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();
            }
        }
        public E removeFirst() {
            E x = pollFirst();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
    
        public E removeLast() {
            E x = pollLast();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
    
        public E pollFirst() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                return unlinkFirst();
            } finally {
                lock.unlock();
            }
        }
    
        public E pollLast() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                return unlinkLast();
            } finally {
                lock.unlock();
            }
        }
    
        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();
            }
        }
    
        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();
            }
        }
    
        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();
            }
        }
    
        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();
            }
        }
    
        public E getFirst() {
            E x = peekFirst();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
        public E getLast() {
            E x = peekLast();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
    
        public E peekFirst() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                return (first == null) ? null : first.item;
            } finally {
                lock.unlock();
            }
        }
    
        public E peekLast() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                return (last == null) ? null : last.item;
            } finally {
                lock.unlock();
            }
        }
    
        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();
            }
        }
    
        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();
            }
        }
    
        public boolean add(E e) {
            addLast(e);
            return true;
        }
    
    
        public boolean offer(E e) {
            return offerLast(e);
        }
    
     
        public void put(E e) throws InterruptedException {
            putLast(e);
        }
    
     
        public boolean offer(E e, long timeout, TimeUnit unit)
            throws InterruptedException {
            return offerLast(e, timeout, unit);
        }
    
    
        public E remove() {
            return removeFirst();
        }
    
        public E poll() {
            return pollFirst();
        }
    
        public E take() throws InterruptedException {
            return takeFirst();
        }
    
        public E poll(long timeout, TimeUnit unit) throws InterruptedException {
            return pollFirst(timeout, unit);
        }
    
     
        public E element() {
            return getFirst();
        }
    
        public E peek() {
            return peekFirst();
        }
        public int remainingCapacity() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                return capacity - count;
            } finally {
                lock.unlock();
            }
        }
        public int drainTo(Collection<? super E> c) {
            return drainTo(c, Integer.MAX_VALUE);
        }
    
        public int drainTo(Collection<? super E> c, int maxElements) {
            if (c == null)
                throw new NullPointerException();
            if (c == this)
                throw new IllegalArgumentException();
            if (maxElements <= 0)
                return 0;
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                int n = Math.min(maxElements, count);
                for (int i = 0; i < n; i++) {
                    c.add(first.item);   // In this order, in case add() throws.
                    unlinkFirst();
                }
                return n;
            } finally {
                lock.unlock();
            }
        }
        public void push(E e) {
            addFirst(e);
        }
    
     
        public E pop() {
            return removeFirst();
        }
    
        public boolean remove(Object o) {
            return removeFirstOccurrence(o);
        }
    
        public int size() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                return count;
            } finally {
                lock.unlock();
            }
        }
        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();
            }
        }
    
        @SuppressWarnings("unchecked")
        public Object[] toArray() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] a = new Object[count];
                int k = 0;
                for (Node<E> p = first; p != null; p = p.next)
                    a[k++] = p.item;
                return a;
            } finally {
                lock.unlock();
            }
        }
    
       
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                if (a.length < count)
                    a = (T[])java.lang.reflect.Array.newInstance
                        (a.getClass().getComponentType(), count);
    
                int k = 0;
                for (Node<E> p = first; p != null; p = p.next)
                    a[k++] = (T)p.item;
                if (a.length > k)
                    a[k] = null;
                return a;
            } finally {
                lock.unlock();
            }
        }
    
        public String toString() {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Node<E> p = first;
                if (p == null)
                    return "[]";
    
                StringBuilder sb = new StringBuilder();
                sb.append('[');
                for (;;) {
                    E e = p.item;
                    sb.append(e == this ? "(this Collection)" : e);
                    p = p.next;
                    if (p == null)
                        return sb.append(']').toString();
                    sb.append(',').append(' ');
                }
            } finally {
                lock.unlock();
            }
        }
    
        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();
            }
        }
    
        public Iterator<E> iterator() {
            return new Itr();
        }
    
        public Iterator<E> descendingIterator() {
            return new DescendingItr();
        }
    
        /**
         * Base class for Iterators for LinkedBlockingDeque
         */
        private abstract class AbstractItr implements Iterator<E> {
    
            Node<E> next;
            E nextItem;
            private Node<E> lastRet;
    
            abstract Node<E> firstNode();
            abstract Node<E> nextNode(Node<E> n);
    
            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();
                }
            }
            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);
                    if (s == null)
                        return null;
                    else if (s.item != null)
                        return s;
                    else if (s == n)
                        return firstNode();
                    else
                        n = s;
                }
            }
            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();
                }
            }
    
            public boolean hasNext() {
                return next != null;
            }
    
            public E next() {
                if (next == null)
                    throw new NoSuchElementException();
                lastRet = next;
                E x = nextItem;
                advance();
                return x;
            }
    
            public void remove() {
                Node<E> n = lastRet;
                if (n == null)
                    throw new IllegalStateException();
                lastRet = null;
                final ReentrantLock lock = LinkedBlockingDeque.this.lock;
                lock.lock();
                try {
                    if (n.item != null)
                        unlink(n);
                } finally {
                    lock.unlock();
                }
            }
        }
        private class Itr extends AbstractItr {
            Node<E> firstNode() { return first; }
            Node<E> nextNode(Node<E> n) { return n.next; }
        }
        private class DescendingItr extends AbstractItr {
            Node<E> firstNode() { return last; }
            Node<E> nextNode(Node<E> n) { return n.prev; }
        }
        static final class LBDSpliterator<E> implements Spliterator<E> {
            static final int MAX_BATCH = 1 << 25;  // max batch array size;
            final LinkedBlockingDeque<E> queue;
            Node<E> current;    // current node; null until initialized
            int batch;          // batch size for splits
            boolean exhausted;  // true when no more nodes
            long est;           // size estimate
            LBDSpliterator(LinkedBlockingDeque<E> queue) {
                this.queue = queue;
                this.est = queue.size();
            }
    
            public long estimateSize() { return est; }
    
            public Spliterator<E> trySplit() {
                Node<E> h;
                final LinkedBlockingDeque<E> q = this.queue;
                int b = batch;
                int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
                if (!exhausted &&
                    ((h = current) != null || (h = q.first) != null) &&
                    h.next != null) {
                    Object[] a = new Object[n];
                    final ReentrantLock lock = q.lock;
                    int i = 0;
                    Node<E> p = current;
                    lock.lock();
                    try {
                        if (p != null || (p = q.first) != null) {
                            do {
                                if ((a[i] = p.item) != null)
                                    ++i;
                            } while ((p = p.next) != null && i < n);
                        }
                    } finally {
                        lock.unlock();
                    }
                    if ((current = p) == null) {
                        est = 0L;
                        exhausted = true;
                    }
                    else if ((est -= i) < 0L)
                        est = 0L;
                    if (i > 0) {
                        batch = i;
                        return Spliterators.spliterator
                            (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
                             Spliterator.CONCURRENT);
                    }
                }
                return null;
            }
    
            public void forEachRemaining(Consumer<? super E> action) {
                if (action == null) throw new NullPointerException();
                final LinkedBlockingDeque<E> q = this.queue;
                final ReentrantLock lock = q.lock;
                if (!exhausted) {
                    exhausted = true;
                    Node<E> p = current;
                    do {
                        E e = null;
                        lock.lock();
                        try {
                            if (p == null)
                                p = q.first;
                            while (p != null) {
                                e = p.item;
                                p = p.next;
                                if (e != null)
                                    break;
                            }
                        } finally {
                            lock.unlock();
                        }
                        if (e != null)
                            action.accept(e);
                    } while (p != null);
                }
            }
    
            public boolean tryAdvance(Consumer<? super E> action) {
                if (action == null) throw new NullPointerException();
                final LinkedBlockingDeque<E> q = this.queue;
                final ReentrantLock lock = q.lock;
                if (!exhausted) {
                    E e = null;
                    lock.lock();
                    try {
                        if (current == null)
                            current = q.first;
                        while (current != null) {
                            e = current.item;
                            current = current.next;
                            if (e != null)
                                break;
                        }
                    } finally {
                        lock.unlock();
                    }
                    if (current == null)
                        exhausted = true;
                    if (e != null) {
                        action.accept(e);
                        return true;
                    }
                }
                return false;
            }
    
            public int characteristics() {
                return Spliterator.ORDERED | Spliterator.NONNULL |
                    Spliterator.CONCURRENT;
            }
        }
    
        public Spliterator<E> spliterator() {
            return new LBDSpliterator<E>(this);
        }
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                // Write out capacity and any hidden stuff
                s.defaultWriteObject();
                // Write out all elements in the proper order.
                for (Node<E> p = first; p != null; p = p.next)
                    s.writeObject(p.item);
                // Use trailing null as sentinel
                s.writeObject(null);
            } finally {
                lock.unlock();
            }
        }
    
        private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            s.defaultReadObject();
            count = 0;
            first = null;
            last = null;
            // Read in all elements and place in queue
            for (;;) {
                @SuppressWarnings("unchecked")
                E item = (E)s.readObject();
                if (item == null)
                    break;
                add(item);
            }
        }
    
    }

[Java]: http://lib.csdn.net/base/javaee
[20160706172122975]: /images/20220716/408e94f23a1b48cc966031e842a35f03.png