Java優(yōu)先級(jí)隊(duì)列是與隊(duì)列有些相似的數(shù)據(jù)結(jié)構(gòu)。不同之處在于元素的處理方式：

標(biāo)準(zhǔn)隊(duì)列嚴(yán)格遵循 FIFO(先進(jìn)后出)原則。

優(yōu)先級(jí)隊(duì)列不遵循先進(jìn)先出原則。

在優(yōu)先級(jí)隊(duì)列中，根據(jù)優(yōu)先級(jí)從隊(duì)列中刪除元素。 這轉(zhuǎn)化為以下要求：

優(yōu)先級(jí)隊(duì)列中的每個(gè)元素都必須有一個(gè)與之關(guān)聯(lián)的優(yōu)先級(jí)。正如您可能已經(jīng)猜到的那樣，具有最高優(yōu)先級(jí)的元素會(huì)從隊(duì)列中移除(出隊(duì))。

但是應(yīng)該如何定義隊(duì)列中元素的優(yōu)先級(jí)呢?

定義元素的優(yōu)先級(jí)

基本上，您有兩種選擇來(lái)定義隊(duì)列中元素的優(yōu)先級(jí)。你可以

根據(jù)元素的自然順序?qū)υ剡M(jìn)行排序。

使用自定義比較器對(duì)元素進(jìn)行排序。

在本文中，我們將重點(diǎn)介紹如何實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。因此，為簡(jiǎn)單起見(jiàn)，我們將根據(jù)元素的自然順序?qū)υ剡M(jìn)行排序。

在我們的示例中，優(yōu)先級(jí)隊(duì)列將被限制為 int，因此自然排序非常好。但是，請(qǐng)記住，這僅用于演示目的。

如果您要在現(xiàn)實(shí)生活中實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，您可能想要使用泛型——或者像任何其他開(kāi)發(fā)人員一樣使用內(nèi)置的java.util.PriorityQueue。

為了使我們的示例實(shí)現(xiàn)符合 Java 規(guī)范，最小 元素被定義為具有最高優(yōu)先級(jí)的元素。

優(yōu)先隊(duì)列操作

任何隊(duì)列實(shí)現(xiàn)的最基本操作集是：

enqueue — 將元素插入隊(duì)列。

dequeue — 從隊(duì)列中移除一個(gè)元素。

isEmpty — 如果隊(duì)列為空，則返回 true。

size — 返回隊(duì)列中元素的大小/數(shù)量。

contains — 如果隊(duì)列包含給定元素，則返回 true。

peek — 返回隊(duì)列的最前面的元素，不 移除它。

請(qǐng)注意，優(yōu)先級(jí)隊(duì)列的 Java 實(shí)現(xiàn)對(duì)方法使用不同的名稱。在生產(chǎn)環(huán)境中，我強(qiáng)烈建議您使用優(yōu)先級(jí)隊(duì)列的默認(rèn)實(shí)現(xiàn)，而不是“家庭成長(zhǎng)”它。

優(yōu)先隊(duì)列的實(shí)現(xiàn)

現(xiàn)在，讓我們?cè)?Java 中實(shí)現(xiàn)一個(gè)非泛型優(yōu)先級(jí)隊(duì)列。我們將一次實(shí)現(xiàn)一個(gè)操作，但首先，我們必須決定 要使用哪種內(nèi)部數(shù)據(jù)結(jié)構(gòu)。

數(shù)組非常好，所以我們將繼續(xù)使用它。

對(duì)于熟悉數(shù)組的人來(lái)說(shuō)，您可能知道數(shù)組在 Java 中具有固定大小。我們對(duì)這個(gè)問(wèn)題的解決方案是我們將提供一個(gè)私有方法 double()， 它“增加”了數(shù)組的容量。

優(yōu)先級(jí)隊(duì)列的代碼框架如下所示。

package priorityqueue;
public class PriorityQueue {
    private int[] innerArray;
    private int size;
    public PriorityQueue() {
        this.innerArray = new int[10];
        size = 0;
    }
    public void enqueue(int x) {
    }
    public int dequeue() {
        return 0;
    }
    public int peek() {
        return 0;
    }
    public boolean contains(int x) {
        return false;
    }
    public boolean isEmpty() {
        return false;
    }
    public int size() {
        return 0;
    }
    private void doubleArray() {
    }
}

如您所見(jiàn)，我們使用int數(shù)組作為內(nèi)部數(shù)據(jù)結(jié)構(gòu)，并在構(gòu)造函數(shù)中將其默認(rèn)大小初始化為 10。我們還提供了一個(gè)私有變量size來(lái)跟蹤元素的數(shù)量。