优先队列！我们来分解一下，了解一下数据结构的这一部分。

队列

队列与堆栈一样，是列表的特化。它是建立在先进先出的基础上的——先进先出，这意味着先进先出。换句话说，队列中“最年长”的人先离开，为了更好地理解，请考虑银行队列。

⚠️

队列应用：操作系统中的进程管理；并发编程中任务之间的通信；计算机网络（打印）；响应 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();
}
</e>

优先队列

这类似于日常排队的行为，但现在考虑一下您在银行排队，一位女士进入队列，每个人都让她先进，因为她年纪更大，所以有更大的优先级。

在优先级队列数据结构中，每个节点都有一个Key-Value，Key是存储其优先级的键，Value是节点的值。默认情况下，Java 中的 Key 最初是数字，程序员可以稍后更改。

Key和Value的集合称为Entry，所以这个E.D的接口发生了变化。其他细节是：Key一旦定义，就不能更改。如果两个节点的 Key 中的优先级值相同，则程序员选择规则。

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

在接下来的结构中，我们将使用 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();
}
</e>

第三步 → 如果它不是列表中的唯一元素，则必须检查新节点是否比第一个节点具有更高的优先级。

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

第三步 → 然后与列表中的最后一个元素进行比较

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)



<p>第二步 → 然后，由于您已经要消除第一个节点，只需将 First 指向 First 旁边的节点即可<br>
</p>

<pre class="brush:php;toolbar:false">             }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> max = maxPriority();
</k>

最大优先级

返回列表中优先级最高的元素的方法，由于我们是按顺序排列的，因此它只返回第一个元素。

        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();
}
</e>

第二步→如果不为空，只需在最后添加这个节点即可！

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

最大优先级

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)



<p>第二步 → 然后检查它是否是唯一的元素，如果是，则 F 和 L 为空！<br>
</p>

<pre class="brush:php;toolbar:false">             }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;
            }
        }

第四步 → 如果它在中间，则必须移除人群中的最大值，当没有其他人指向它时，就会发生这种情况。

        Entry<k> max = maxPriority();
</k>

渐进分析

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

以上是优先队列！我们来分解一下，了解一下数据结构的这一部分。的详细内容。更多信息请关注PHP中文网其他相关文章！