java PriorityBlockingQueue出队方法

本教程操作环境：windows7系统、java10版，DELL G3电脑。

1.出队过程

（1）加锁；

（2）判断是否出队成功，未成功就阻塞在notEmpty条件上；

（3）出队时弹出堆顶元素，并把堆尾元素拿到堆顶；

（4）再做自上而下的堆化；

（5）解锁；

2.出队方法

出队方法有 poll(), take(), poll(long timeout, TimeUnit unit)，peek()

poll 和 peek 与之前类似，这里不做说明。

publicEtake()throwsInterruptedException{
//获取锁，可被中断
finalReentrantLocklock=this.lock;
lock.lockInterruptibly();
Eresult;
try{
//如果队列为空，则阻塞，把当前线程放入notEmpty的条件队列
while((result=dequeue())==null)
notEmpty.await();//阻塞当前线程
}finally{
lock.unlock();//释放锁
}
returnresult;
}
privateEdequeue(){
intn=size-1;
if(n<0)
returnnull;
else{
Object[]array=queue;
Eresult=(E)array[0];//弹出堆顶元素
Ex=(E)array[n];//把堆尾元素拿到堆顶
array[n]=null;
Comparator<?superE>cmp=comparator;
if(cmp==null)//自上而下的堆化
siftDownComparable(0,x,array,n);
else
siftDownUsingComparator(0,x,array,n,cmp);
size=n;
returnresult;
}
}
privatestatic<T>voidsiftDownComparable(intk,Tx,Object[]array,
intn){
if(n>0){
Comparable<?superT>key=(Comparable<?superT>)x;
inthalf=n>>>1;
//只需要遍历到叶子节点就够了
while(k<half){
//左子节点
intchild=(k<<1)+1;
//左子节点的值
Objectc=array[child];
//右子节点
intright=child+1;
//取左右子节点中最小的值
if(right<n&&
((Comparable<?superT>)c).compareTo((T)array[right])>0)
c=array[child=right];
//key如果比左右子节点都小，则堆化结束
if(key.compareTo((T)c)<=0)
break;
//否则，交换key与左右子节点中最小的节点的位置
array[k]=c;
k=child;
}
//找到了放元素的位置，放置元素
array[k]=key;
}
}

原文来自：https://www.py.cn