Java優先級隊列是與隊列有些相似的數據結構。不同之處在于元素的處理方式：

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

優先級隊列不遵循先進先出原則。

在優先級隊列中，根據優先級從隊列中刪除元素。 這轉化為以下要求：

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

但是應該如何定義隊列中元素的優先級呢?

定義元素的優先級

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

根據元素的自然順序對元素進行排序。

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

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

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

如果您要在現實生活中實現優先級隊列，您可能想要使用泛型——或者像任何其他開發人員一樣使用內置的java.util.PriorityQueue。

為了使我們的示例實現符合 Java 規范，最小 元素被定義為具有最高優先級的元素。

優先隊列操作

任何隊列實現的最基本操作集是：

enqueue — 將元素插入隊列。

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

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

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

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

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

請注意，優先級隊列的 Java 實現對方法使用不同的名稱。在生產環境中，我強烈建議您使用優先級隊列的默認實現，而不是“家庭成長”它。

優先隊列的實現

現在，讓我們在 Java 中實現一個非泛型優先級隊列。我們將一次實現一個操作，但首先，我們必須決定 要使用哪種內部數據結構。

數組非常好，所以我們將繼續使用它。

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

優先級隊列的代碼框架如下所示。

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數組作為內部數據結構，并在構造函數中將其默認大小初始化為 10。我們還提供了一個私有變量size來跟蹤元素的數量。