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

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等方法都会调用上面的核心方法。而且实现上面也是比较简单的。就是双端链表的基本操作。不懂的可以画画图帮助理解哈。

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

分享到 :
相关推荐

张小娴小说有哪些(爱情导师张小娴)

请用语音读文章张小娴十大经典小说1、面包树上的女人《面包树上的女人》是一本20[&h...

玄幻小说排行榜(十大经典玄幻小说)

请用语音读文章玄幻小说一直都是网络小说中最热门的一个分类。今天讲解十本已经完本的读[...

家庭剧电影排行榜前十名(好看的电视剧排行榜前十名)

请用语音读文章随着电影事业的蓬勃发展。越来越多的电影种类诞生。电影作为一种介质。总[...

搞笑电影排行榜前十名2021(中国搞笑电影排行榜前十名)

请用语音读文章最近一部。让你笑到面膜裂掉、喷饭键盘的喜剧片。是哪一部?自从周星驰[&...

发表评论

您的电子邮箱地址不会被公开。