Java 优先队列

1 年 ago

文, 翔

2 minutes

不时地，我们需要按照特定顺序处理队列中的项目。优先队列是一种可以完成此工作的数据结构。Java优先队列与“普通”队列不同。它按照项目的优先级检索项目，而不是按照“先进先出”原则。

Java的优先队列

Java优先队列的构造函数

Java 优先队列的构造函数有以下几种选项

PriorityQueue（SortedSet c）-创建包含指定排序集合中的元素的优先级队列

优先队列元素按自然顺序排序，除非在创建时提供了比较器。默认情况下，元素按升序排序，因此队列的头元素是优先级最低的元素。如果有两个元素在同一时间具备成为头元素的资格，这种情况会任意地被打破。

Java优先级队列示例

让我们创建一个包含各种任务的优先队列。

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

这将创建一个任务的优先级队列，它将按照字符串的自然顺序进行排序。让我们再创建一个按照自然顺序的相反顺序排序任务的优先级队列。因此，我们需要传递一个比较器。

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java优先队列的方法

现在，让我们来看看PriorityQueue提供的所有方法，并使用它们：

Comparator comparator() – 这个方法返回用于排序队列元素的比较器。如果没有指定比较器并且队列按照元素的自然顺序排序，则返回null。因此，如果我们执行以下代码：
System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

输出将为：
null
java.util.Collections$ReverseComparator@15db9742

boolean contains(Object o) – 如果队列包含指定的元素，则返回true。让我们检查一下“task3”是否属于Priority队列tasks：
System.out.println(tasks.contains(“task3”));

这将打印：
true

boolean offer(E e) – 这个方法和add()方法一样，也向队列中添加一个元素。offer()和add()方法在容量受限队列的情况下实际上有一些差异，但在PriorityQueue的情况下，它们是相同的。与add()不同，即使无法将元素添加到队列中，offer()也不会抛出异常。

E peek() – 检索队列的头部，如果队列为空则返回null。换句话说，它返回具有最高优先级的元素。因此，下面的代码：
System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

将输出：
task1
task5

E poll() – 这个方法也检索队列的头部（具有最高优先级的元素），如果队列为空则返回null。但与peek()不同，它还会删除该元素。因此，如果我们调用poll()：
System.out.println(“在tasks上进行Poll：” + tasks.poll());
System.out.println(“在reverseTasks上进行Poll：” + reverseTasks.poll());

然后再次调用peek：
System.out.println(“在tasks上进行Peek：” + tasks.peek());
System.out.println(“在reverseTasks上进行Peek：” + reverseTasks.peek());

我们将会输出：
在tasks上进行Poll：task1
在reverseTasks上进行Poll：task5
在tasks上进行Peek：task2
在reverseTasks上进行Peek：task4

int size() – 返回队列中的元素数量。

boolean remove(Object o) – 从队列中删除指定的元素（如果存在）。如果存在两个相同的元素，它只会删除其中一个。

Object[] toArray() – 返回包含队列中所有元素的数组。

T[] toArray(T[] a) – 返回包含队列中所有元素的数组，返回数组的类型与指定数组的类型相同。

Iterator iterator() – 返回队列的迭代器。

void clear() – 从队列中移除所有元素。

除此之外，优先队列还继承了集合和对象类的方法。

Java优先队列的时间复杂度

对于检索方法，它具有常数时间复杂度

这个优先队列的实现不是线程安全的。因此，如果我们需要同步访问，我们需要使用PriorityBlockingQueue。参考：API文档。