優先隊列！讓我們來分解一下，了解一下資料結構的這一部分。-java教程-PHP中文網

Priority Queue! Vamos destrinchar e aprender sobre essa parte de Estrutura de Dados.

佇列

佇列與堆疊一樣，是列表的特化。它是建立在先進先出的基礎上的——先進先出，這意味著先進先出。換句話說，隊列中「最年長」的人先離開，為了更好地理解，請考慮銀行隊列。

⚠️

佇列應用：作業系統中的進程管理；並發程式設計中任務之間的通訊；電腦網路（列印）；回應 Web 伺服器上的請求

佇列本身只允許在末端直接操作資料。

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

登入後複製

優先隊列

這類似於日常排隊的行為，但現在考慮一下您在銀行排隊，一位女士進入隊列，每個人都讓她先進，因為她年紀更大，所以有更大的優先級。

在優先權佇列資料結構中，每個節點都有一個Key-Value，Key是儲存其優先權的鍵，Value是節點的值。預設情況下，Java 中的 Key 最初是數字，程式設計師可以稍後更改。

Key和Value的集合稱為Entry，所以這個E.D的介面改變了。其他細節是：Key一旦定義，就不能更改。如果兩個節點的 Key 中的優先權值相同，則程式設計師選擇規則。

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

登入後複製

在接下來的結構中，我們將使用 Node 和 Entry 類別、first、last 和 size 屬性以及 CompareTo

優先權佇列分為兩種：已排序（Sorted Priority Queue）和未排序（Unorted Priority Queue）

排序優先權佇列

有序列表負責將節點插入到正確的位置，因此刪除很容易，只需刪除第一個（如果執行 E.D 的程式設計師定義最高優先元素應該位於開頭）

為了知道哪個節點具有最高優先級，我們使用compareTo，這是一個集合函數，透過它的返回，我們可以獲得執行此 E.D 的關鍵結果，如果返回是：

否定：如果呼叫該方法的物件比作為參數傳遞的物件「小」。
零：如果物件相等。
正：如果呼叫方法的物件比作為參數傳遞的物件「更大」。

插入

要進入，您必須檢查一些事項

第一步 → 建立一個新節點

Node newNode = new Node(key, value)

登入後複製

第二步 → 檢查 Queue 是否為空，如果是，則將 Head 和 Last 作為新節點，考慮到它將是唯一的

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

登入後複製

第三步 → 如果它不是清單中的唯一元素，則必須檢查新節點是否比第一個節點具有更高的優先權。

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

登入後複製

第三步 → 然後與列表中的最後一個元素進行比較

Node newNode = new Node(key, value)

登入後複製

第四步 → 如果沒有其他的，就只剩下中間了！為此，我們需要製作一個輔助節點放在 newNode (nN) 的前面並比較兩者，當 auxNode 指向空時，或者當 nN 大於 auxNode 時（較大，因此它），比較結束排在後面）。這個 while 用於 aux 四處比較兩個節點的值，當找到時，將 nN 放在 auxNode 後面

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

登入後複製

消除

Sorted 中的刪除方法要簡單得多，因為正如已經提到的，佇列已經為其組織好了。

第一步 → 由於每個 Remove 方法都會傳回要刪除的元素，因此該步驟將建立 Entry （為什麼不是節點？）

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

登入後複製

第二步 → 然後，由於您已經要消除第一個節點，只需將 First 指向 First 旁邊的節點即可

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

登入後複製

第三步 → 檢查佇列中是否只有一個元素，因為如果是，佇列將為空！然後你必須將 F 和 L 設為 null

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

登入後複製

第四步 → 如果不是唯一的元素，則表示還有其他元素！因此，當您在步驟 2 中刪除第一個時，先前的第一個仍然與前一個連接，所以我們必須：

        Entry<K,V> max = maxPriority();

登入後複製

最大優先權

傳回清單中優先順序最高的元素的方法，由於我們是按順序排列的，因此它只傳回第一個元素。

        first = first.next;

登入後複製

漸進分析

Método	O(_)
size	O(1)
isEmpty	O(1)
insert	O(n)
remove	O(1)
maxPriority	O(1)

未排序的優先權佇列

無序隊列和有序隊列有很大不同！讓我們從他的方法開始：

插入

要加入unsorted、like和disordered中，你不需要擔心這個新元素會在哪裡，只需將它加到最後即可！

第一步→檢查清單是否為空，因為如果是，則要新增的節點將是第一個（First）和最後一個（Last）

public interface Queue<E> {
    void enqueue(E value); //enfileira
    E dequeue(); //remove e desenfileira
    E first(); //retorna primeiro elemento
    int size(); //algumas literaturas se chama lenght()
    boolean isEmpty();
}

登入後複製

第二步→如果不為空，只要在最後加上這個節點即可！

public interface PriorityQueueOg<K,V> {
    void insert(K key, V value);
    Entry<K,V> remove();
    int size();
    boolean isEmpty();
}

登入後複製

最大優先權

Unsorted 中的移除比 Sorted 中的那幾行程式碼複雜得多...

「為什麼？」你問，我們應該使用一種名為 maxPriority 的方法（在其他版本中也簡單得多），其目標是找到具有最高優先級的節點。以前是用簡單的幾行程式碼來教導的，現在，因為我們不知道這個最高優先權的節點實際上在哪裡，所以我們必須遍歷整個佇列來尋找它！因此，在我們研究remove本身之前，我們先來看看maxPriority。

第一步→ 每當我們想要遍歷一個資料結構時，我們需要兩個節點：一個是始終前進的輔助節點，另一個是我們想要實現的節點（在本例中是MaxPriority）

Node newNode = new Node(key, value)

登入後複製

第二步 → 這兩個將在一個節點內運行，只有當 aux 達到 null（隊列末尾）時才結束。比較這些節點，如果為負數，表示aux小於max，所以max最大，更新max節點的值，然後讓aux運行。

        if(isEmpty()){
            first = newNode;
            last = newNode;
        }else{

登入後複製

消除

第一步 → 在所有 emove 中，建立一個變數來儲存將被刪除的節點。在這種情況下，您已經知道哪一個將被刪除，因為您正在呼叫 maxPriority
方法

         if(compare(newNode, first)<0){
                 //Se o nN for menor que o F
                 //Levando em consideração que a prioridade maior é 0
                 //Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
                newNode.next = first;
                first.previous = newNode;
                first = newNode;
          }

登入後複製

第二步 → 然後檢查它是否是唯一的元素，如果是，則 F 和 L 為空！

             }else if(compare(newNode, last)>=0){
           //Se o nN for maior que o L
           //Significa que o número de nN é maior que L
           //Então bota o nN para ultimo
                newNode.previous=last;
                last.next=newNode;
                last = newNode;
            }else{

登入後複製

第3步→如果不是唯一的，還有其他選擇：如果max是最後一個，則消除最後一個，如果是第一個，則消除第一個，如果不是兩個兩個，則在中間！

            }else{
                //se nao for nada, está no meio
                //entao temos que achar entre qual dos meios
                Node auxNode = first;
                while(compare(newNode, auxNode)>0 && auxNode.next!=null){
                    //enquanto o newNode tiver prioridade maior que o auxiliar
                    //e o auxiliar tiver um proximo
                    auxNode = auxNode.next;
                }
                newNode.next = auxNode;
                newNode.previous = auxNode.previous;
            }
        }

登入後複製

第四步 → 如果它在中間，則必須移除人群中的最大值，當沒有其他人指向它時，就會發生這種情況。