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

標準隊列嚴格遵循 FIFO(先進后出)原則。

優(yōu)先級隊列不遵循先進先出原則。

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

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

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

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

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

根據(jù)元素的自然順序對元素進行排序。

使用自定義比較器對元素進行排序。

在本文中，我們將重點介紹如何實現(xiàn)優(yōu)先級隊列。因此，為簡單起見，我們將根據(jù)元素的自然順序對元素進行排序。

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

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

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

優(yōu)先隊列操作

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

enqueue — 將元素插入隊列。

dequeue — 從隊列中移除一個元素。

isEmpty — 如果隊列為空，則返回 true。

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

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

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

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

優(yōu)先隊列的實現(xiàn)

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

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

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

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

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() {
    }
}

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