Java优先级队列概述

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来跟踪元素的数量。