Java|什么是Java PriorityQueue? Java

文章图片

文章图片

PriorityQueue 是构建在无界优先级队列和优先级堆上的重要 Java API 之一，本文介绍了有关此 API的一些复杂信息。

概述
PriorityQueue 类是 java.util 包的一部分，是 Java 中基于优先级的队列的通用实现。队列基本上是一种数据结构，它定义了从商店中插入和检索项目的过程的特定规范。这个想法与许多人排队等候买票非常相似。第一个站在队列中的人有第一个机会获得门票，最后一个人有机会在最后获得一个机会。人们被添加到队列的末尾或尾部。向队列中添加项在技术上称为入队过程，从队列中删除的项是从行中的第一个开始的。这称为出队。这个想法是以 FIFO(先进先出)的方式对元素进行排序。
现在，这是最简单的架构，并且严格定义了队列的实际含义以及如何在计算机中对其进行模拟。存储通常由一个简单的数组表示，其中存储和检索过程具有此定义的规范。优先级队列在此之上施加了一些特殊规范。

队列的Java实现
Java API 在 java.util 包中有一个通用接口名称 Queue<E> 。这是 Java 集合框架 API 的一部分，旨在在处理之前保存元素。作为 Collection 的一部分，它具有所有基本的 Collection 操作。特定于其身份的操作处理存储在其中的元素的插入、提取和检查。这些操作中的每一个都有两种不同的形式，例如，一种在操作失败时抛出异常，另一种根据操作返回特殊值，例如 null 或 false 。请注意，与典型队列不同， Java 队列的具体实现不一定以 FIFO 方式对元素进行排序。对于基于优先级的队列尤其如此，其中元素的排序是根据提供的比较器或自然排序完成的。但无论排序如何， remove() 或 poll() 方法总是会检索队列头部的元素。这两种不太可能的方法之间的具体区别似乎是一种相似的方法，一种在失败时抛出异常(NoSuchElementException) ，而后者则返回(null) ，一个特殊的值。
【Java|什么是Java PriorityQueue?】

请注意， Queue<E> 接口不适合在并发编程中使用，因为它没有定义阻塞队列方法，在这些方法中，入队和出队进程等待元素出现在队列中或大小可用，就此而言。有一个特定的接口，称为 BlockingQueue<E> ，它扩展了 Queue<E> 接口并解决了这些问题。
有一个抽象类，称为 AbstractQueue<E> ，它提供了一些队列操作的部分实现。 PriorityQueue<E> 类是这个抽象类的直接扩展。
优先队列
优先级队列的 Java 实现是一种特殊类型的队列，其中元素的排序由其自然排序原则确定或根据创建期间提供的 Comparator 进行定制。我们在构造过程中调用的构造函数决定了与优先队列一起使用的排序原则。与不允许空元素的 Queue<E> 不同，但某些实现(例如 LinkedList)也不禁止插入空元素。然而， PriorityQueue<E> 根本不允许空元素。如果优先级队列是按照自然顺序构造的，那么任何不可比较的元素插入都会抛出 ClassCastException 。
它被声明为无界的并且基于优先级堆。尽管队列的大小被称为无界，但有一个内部容量来确定数组的大小。随着元素的插入，这个大小会自动增长。但是，没有详细说明增大尺寸的原理。
有七种类型的重载构造函数，我们可以通过它们设置参数来指定队列的初始容量，提供 Comparator 来指定元素的自定义顺序，或者使用无参数构造函数接受所有内容作为默认值。
PriorityQueue()
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity Comparator<? Super E> comparator)
PriorityQueue(Commection<? extends E> c)
PriorityQueue(Comparator<? Super E> comparator)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)
与 Queue<E> 类似， PriorityQueue<E> 也不是同步的，因此在并发编程中应谨慎使用。但是，有一个同步的替代方案，称为 PriorityBlockingQueue 。这与 PriorityQueue<E> 的工作方式相同，只是具有线程安全的附加条件。
PriorityQueue<E> 中定义的操作与 Queue<E> 相同，只是添加了一些内容。

结论
优先级队列的附加规范是从列表中删除的项目具有最高优先级。 Java 将优先级规则强加到其他正常队列的方式是附加元素的排序原则。此顺序可以根据程序员的要求进行定制，也可以设置为默认值。这就是 Java 中优先级队列实现的本质。