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

请用语音读文章

LinkedBlockingDeque概述

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;
else
f.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;
else
l.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;//helpGC
first=n;
if(n==null)
last=null;
else
n.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;//helpGC
last=p;
if(p==null)
first=null;
else
p.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;
//移除的是first
if(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等方法都会调用上面的核心方法。而且实现上面也是比较简单的。就是双端链表的基本操作。不懂的可以画画图帮助理解哈。

以上就是由优质生活领域创作者 生活常识网 整理编辑的，如果觉得有帮助欢迎收藏转发~