中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Java并發編程中的優先級隊列PriorityBlockingQueue怎么使用

發布時間:2023-05-05 10:09:54 來源:億速云 閱讀:101 作者:iii 欄目:開發技術

這篇文章主要介紹“Java并發編程中的優先級隊列PriorityBlockingQueue怎么使用”,在日常操作中,相信很多人在Java并發編程中的優先級隊列PriorityBlockingQueue怎么使用問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”Java并發編程中的優先級隊列PriorityBlockingQueue怎么使用”的疑惑有所幫助!接下來,請跟著小編一起來學習吧!

    PriorityBlockingQueue是Java中實現了堆數據結構的線程安全的有界阻塞隊列。它可以在多線程場景下安全地進行元素添加、刪除和獲取操作,而且可以根據元素的優先級進行排序。

    一、PriorityBlockingQueue概述

    PriorityBlockingQueue類實現了BlockingQueue接口,它是一個線程安全的隊列,繼承自AbstractQueue類,而AbstractQueue類又實現了Queue接口。PriorityBlockingQueue是一個有界的隊列,其容量可以在構造函數中進行指定,若不指定則默認大小為Integer.MAX_VALUE。同時,PriorityBlockingQueue也支持根據元素的優先級進行排序,這是由于PriorityBlockingQueue內部實現了一個堆數據結構。

    二、PriorityBlockingQueue源碼解析

    1.容器

    PriorityBlockingQueue內部使用了一個Object類型的數組queue來存儲元素,同時使用了一個int類型的變量size來記錄元素的數量。下面是PriorityBlockingQueue類中的定義:

    private transient Object[] queue;
    private transient int size;

    2.比較器

    PriorityBlockingQueue可以根據元素的優先級進行排序,這是由于PriorityBlockingQueue內部維護了一個小根堆或大根堆。在構造函數中,我們可以選擇使用元素自身的比較方式或是自定義比較器來進行元素的排序。若未指定比較器,則PriorityBlockingQueue將使用元素自身的比較方式進行排序。

    private final Comparator<? super E> comparator;

    3.構造函數

    PriorityBlockingQueue提供了多個構造函數,我們可以選擇使用無參構造函數來創建一個默認容量為Integer.MAX_VALUE的PriorityBlockingQueue,或是使用帶有初始容量或自定義比較器的構造函數。下面是PriorityBlockingQueue類的兩個構造函數:

    public PriorityBlockingQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    4.添加元素

    PriorityBlockingQueue中添加元素的方法為offer()方法,它會首先檢查容量是否足夠,如果容量不足則會進行擴容操作,擴容的方式是將原數組長度增加一半。接著,它會將新元素添加到隊列的末尾,并通過siftUp()方法將元素上濾到合適的位置,以維護堆的性質。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        int n, cap;
        Object[] array;
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator; 
            if (n == 0) { array[0] = e; } 
            else { siftUp(n, e, array, cmp); } 
            size = n + 1; notEmpty.signal(); 
        } finally { 
            lock.unlock(); 
        } 
        return true; 
    }

    5.獲取元素

    PriorityBlockingQueue中獲取元素的方法為take()方法,它會首先檢查隊列是否為空,如果隊列為空則會將當前線程阻塞,直到有元素被添加到隊列中。接著,它會獲取隊列的頭部元素,并通過siftDown()方法將隊列的末尾元素移動到頭部,以維護堆的性質。

    public E take() throws InterruptedException { 
        final ReentrantLock lock = this.lock; 
        lock.lockInterruptibly(); 
        E result; 
        try { 
            while (size == 0) notEmpty.await(); 
            result = extract(); 
        } finally {
            lock.unlock(); 
        } 
        return result; 
    }
    private E extract() { 
        final Object[] array = queue; 
        final E result = (E) array[0]; 
        final int n = --size; 
        final E x = (E) array[n]; 
        array[n] = null; 
        if (n != 0) 
        siftDown(0, x, array, comparator); 
        return result; 
    }

    6.維護堆性質

    PriorityBlockingQueue使用小根堆或大根堆來維護元素的優先級,這里我們以小根堆為例。小根堆的特點是父節點的值小于等于左右子節點的值,PriorityBlockingQueue中的堆是通過數組來實現的。當添加元素時,會將新元素添加到隊列的末尾,并通過siftUp()方法將元素上濾到合適的位置,以維護堆的性質。當獲取元素時,會獲取隊列的頭部元素,并通過siftDown()方法將隊列的末尾元素移動到頭部,以維護堆的性質。下面是siftUp()和siftDown()方法的代碼實現:

    private static <T> 
    void siftUp(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        if (cmp != null) 
        siftUpUsingComparator(k, x, array, cmp); 
        else siftUpComparable(k, x, array); 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftUpUsingComparator(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        while (k > 0) { 
            int parent = (k - 1) >>> 1; 
            Object e = array[parent]; 
            if (cmp.compare(x, (T) e) >= 0) 
            break; 
            array[k] = e; 
            k = parent; 
        } 
        array[k] = x; 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftUpComparable(int k, T x, Object[] array) { 
        Comparable<? super T> key = (Comparable<? super T>) x; 
        while (k > 0) { 
            int parent = (k - 1) >>> 1; 
            Object e = array[parent]; 
            if (key.compareTo((T) e) >= 0) 
            break; 
            array[k] = e; 
            k = parent; 
        } 
        array[k] = key; 
    }
    private static <T> 
    void siftDown(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        if (cmp != null) 
        siftDownUsingComparator(k, x, array, cmp); 
        else siftDownComparable(k, x, array); 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftDownUsingComparator(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        int half = size >>> 1; 
        while (k < half) { 
            int child = (k << 1) + 1; 
            Object c = array[child]; 
            int right = child + 1; 
            if (right < size && cmp.compare((T) c, (T) array[right]) > 0) 
            c = array[child = right]; 
            if (cmp.compare(x, (T) c) <= 0) 
            break; 
            array[k] = c; 
            k = child; 
        } 
        array[k] = x; 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftDownComparable(int k, T x, Object[] array) { 
        Comparable<? super T> key = (Comparable<? super T>) x; 
        int half = size >>> 1; 
        while (k < half) { 
            int child = (k << 1) + 1; 
            Object c = array[child]; 
            int right = child + 1; 
            if (right < size && ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) 
            c = array[child = right]; 
            if (key.compareTo((T) c) <= 0) 
            break; 
            array[k] = c; 
            k = child; 
        } 
        array[k] = key; 
    }

    siftUp()方法和siftDown()方法都使用了siftUpUsingComparator()方法和siftDownUsingComparator()方法,它們是使用Comparator來實現堆的上濾和下濾的。當PriorityBlockingQueue沒有指定Comparator時,會使用元素自身的Comparable來實現堆的上濾和下濾。

    到此,關于“Java并發編程中的優先級隊列PriorityBlockingQueue怎么使用”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續學習更多相關知識,請繼續關注億速云網站,小編會繼續努力為大家帶來更多實用的文章!

    向AI問一下細節

    免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

    AI

    九台市| 汶川县| 宕昌县| 胶南市| 江安县| 平果县| 呼伦贝尔市| 浦东新区| 稻城县| 罗田县| 莱州市| 莎车县| 安庆市| 襄汾县| 察隅县| 天镇县| 宁化县| 西林县| 叶城县| 突泉县| 翁源县| 西充县| 扶沟县| 阿城市| 周口市| 余江县| 剑川县| 万源市| 贺州市| 临沭县| 南召县| 山东省| 淮滨县| 布尔津县| 曲靖市| 盱眙县| 交口县| 木里| 九龙坡区| 柳河县| 临澧县|