javaPriorityBlockingQueue出队方法

Z时代
2024-01-10
分类：综合

美女程序员鼓励师

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

1.出队过程

（1）加锁；

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

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

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

（5）解锁；

2.出队方法

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

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

public E take() throws InterruptedException {
    //获取锁，可被中断
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    E result;
    try {
        //如果队列为空，则阻塞，把当前线程放入notEmpty的条件队列
        while ( (result = dequeue()) == null)
            notEmpty.await();//阻塞当前线程
    } finally {
        lock.unlock();//释放锁
    }
    return result;
}
private E dequeue() {
    int n = size - 1;
    if (n < 0)
        return null;
    else {
        Object[] array = queue;
        E result = (E) array[0];// 弹出堆顶元素
        E x = (E) array[n];// 把堆尾元素拿到堆顶
        array[n] = null;
        Comparator<? super E> cmp = comparator;
        if (cmp == null)//自上而下的堆化
            siftDownComparable(0, x, array, n);
        else
            siftDownUsingComparator(0, x, array, n, cmp);
        size = n;
        return result;
    }
}
private static <T> void siftDownComparable(int k, T x, Object[] array,
                                           int n) {
    if (n > 0) {
        Comparable<? super T> key = (Comparable<? super T>)x;
        int half = n >>> 1;           
        // 只需要遍历到叶子节点就够了
        while (k < half) {
            // 左子节点
            int child = (k << 1) + 1; 
            // 左子节点的值
            Object c = array[child];
            // 右子节点
            int right = child + 1;
            // 取左右子节点中最小的值
            if (right < n &&
                ((Comparable<? super T>) 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;
    }
}