Java双端队列 java双端队列作用

LinkedBlockingDeque概述【Java双端队列 java双端队列作用】LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列 。支持O(1)的时间复杂度从两端插入和移除元素 。如不指定边界。则为Integer.MAX_VALUE 。
由一个ReentrantLock保证同步。使用conditions来实现等待通知。

文章插图

文章插图
类图结构及重要字段

文章插图

文章插图
publicclassLinkedBlockingDeque<E>extendsAbstractQueue<E>implementsBlockingDeque<E>,java.io.Serializable{privatestaticfinallongserialVersionUID=-387911632671998426L;/**双向链表节点*/staticfinalclassNode<E>{Eitem;Node<E>prev;Node<E>next;Node(Ex){item=x;}}/***指向第一个节点*Invariant:(first==null&&last==null)||*(first.prev==null&&first.item!=null)*/transientNode<E>first;/***指向最后一个节点*Invariant:(first==null&&last==null)||*(last.next==null&&last.item!=null)*/transientNode<E>last;/**节点数量*/privatetransientintcount;/**队列容量*/privatefinalintcapacity;/**保证同步*/finalReentrantLocklock=newReentrantLock();/**take操作发生的条件*/privatefinalConditionnotEmpty=lock.newCondition();/**put操作发生的条件*/privatefinalConditionnotFull=lock.newCondition();}
linkFirst尝试将节点加入到first之前。更新first 。如果插入之后超出容量。返回false 。
privatebooleanlinkFirst(Node<E>node){//assertlock.isHeldByCurrentThread();if(count>=capacity)returnfalse;Node<E>f=first;node.next=f;first=node;if(last==null)last=node;elsef.prev=node;++count;notEmpty.signal();returntrue;}

文章插图

文章插图
linkLast在last节点后加入节点node 。更新last 。如果插入之后超出容量。返回false 。
privatebooleanlinkLast(Node<E>node){//assertlock.isHeldByCurrentThread();if(count>=capacity)returnfalse;Node<E>l=last;node.prev=l;last=node;if(first==null)first=node;elsel.next=node;++count;notEmpty.signal();//满足notEmpty条件returntrue;}

文章插图

文章插图
unlinkFirst移除first节点。并返回其item值。如果队列为空。则返回full 。
privateEunlinkFirst(){//assertlock.isHeldByCurrentThread();Node<E>f=first;if(f==null)returnnull;Node<E>n=f.next;Eitem=f.item;f.item=null;f.next=f;//helpGCfirst=n;if(n==null)last=null;elsen.prev=null;--count;notFull.signal();//满足notFull条件returnitem;}

文章插图

文章插图
unlinkLast移除last节点。并返回其item值。如果队列为空。则返回full 。
privateEunlinkLast(){//assertlock.isHeldByCurrentThread();Node<E>l=last;if(l==null)returnnull;Node<E>p=l.prev;Eitem=l.item;l.item=null;l.prev=l;//helpGClast=p;if(p==null)first=null;elsep.next=null;--count;notFull.signal();//满足notFull条件returnitem;}

文章插图

文章插图
unlink移除任意一个节点。注意这里并没有操作x本身的连接。因为它可能仍被iterator使用着。
voidunlink(Node<E>x){//assertlock.isHeldByCurrentThread();Node<E>p=x.prev;Node<E>n=x.next;//移除的是firstif(p==null){unlinkFirst();//移除的是last}elseif(n==null){unlinkLast();}else{//移除的是中间节点p.next=n;n.prev=p;x.item=null;//Don'tmesswithx'slinks.Theymaystillbeinuseby//aniterator.//这里x的prev和next指针都没有改变。因为他们可能在被iterator使用--count;notFull.signal();}}

文章插图

文章插图
总结LinkedBlockingDeque是由链表构成的界限可选的双端阻塞队列 。支持O(1)的时间复杂度从两端插入和移除元素 。如不指定边界。则为Integer.MAX_VALUE 。
由一个ReentrantLock保证同步。使用conditions来实现等待通知。
上面介绍的所有操作基本上就是核心方法啦。诸如putFirst、putLast、takeFirst、takeLast等方法都会调用上面的核心方法。而且实现上面也是比较简单的。就是双端链表的基本操作。不懂的可以画画图帮助理解哈。