您的当前位置:首页java PriorityBlockingQueue出队方法

java PriorityBlockingQueue出队方法

2024-08-01 来源:哗拓教育

本教程操作环境: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;
    }
}

以上就是java中PriorityBlockingQueue的出队方法,一般而言我们都是使用take方法进行处理,其它的解决办法,大家也可以在课后进行了解。

显示全文