PriorityQueue是一个FIFO队列吗？

Question

PriorityQueue 实现了 Queue 接口，但是它是否像 Queue 一样是一个 FIFO 数据结构呢？

- ytz

---

它是基于优先级而非顺序的。 - Elbek

Answer 1

从队列接口中可以看到：

队列通常按照FIFO（先进先出）的方式排序元素，但并非一定如此。优先级队列是其中之一，它根据提供的比较器或元素的自然排序对元素进行排序。

因此，PriorityQueue是一种例外，只有当比较器按照这个顺序排序时，它才成为FIFO队列。

- ElderMael

Answer 2

不，它不是。根据Javadoc的说明：

优先级队列的元素按照它们的自然顺序或在队列构建时提供的比较器进行排序，具体取决于使用哪个构造函数。

并且

这个队列的头部是相对于指定排序方式最小的元素。

- kosa

---

+1 概念上顺序可以是先进先出，但通常用于更有趣的事情。 - Peter Lawrey

Answer 3

PriorityQueue（优先队列）不关心先进先出（FIFO）/后进先出（LIFO）。 它处理优先级。 如果有多个具有相同优先级的对象，则不能依赖于任何FIFO LIFO行为。

- Nati

Answer 4

优先队列是一种数据结构，它将元素保持在一致的内部顺序中 - 在Java实现中，此排序在构建时指定。队列的头部和其他元素的顺序由您指定的排序标准确定。

例如，假设您有一个包含学生的PriorityQueue，并且您设置的排序是按年龄升序 - 队列的头部将包含最年轻的学生，尾部将是最年长的学生。当您向PriorityQueue添加学生时，根据他们的年龄，学生将按正确的位置插入，因为这是您指定的排序，它们的插入顺序是不相关的。

- Josh Heald

Answer 5

这取决于您使用的比较器。

例如，假设您正在使用优先队列来管理事件队列，这些事件计划在未来的墙钟时间或概念批处理模式中调用。最高优先级基本上是最早的时间，并且您将使用类似以下的比较器：

first.time < second.time

如果比较器只是比较两个事件的时间，它们将以未定义的顺序出队，并且很可能不是先进先出。

然而，您可以维护Enqueue操作的计数；将其存储在优先级队列元素中；并使您的比较使用队列操作作为tie-breaker。例如：

first.time < second.time || ( first.time == second.time && first.count < second.count )

然后你将获得FIFO行为。如果计数器是32位的，您可以在1000小时内进行1000次入队/秒，然后它会绕回。如果计数器是64位的，则可以在500多年内进行十亿次入队/秒，然后才会绕回。即使计数器绕回，您也可以简单地重新编号所有现有的优先级队列元素：将它们全部出队到一个向量中；对向量进行排序；用其向量元素号覆盖每个向量元素的计数器；并重新插入到优先级队列中。该向量大小成为您的新计数器。

- Swiss Frank

Answer 6

Java中的队列不一定遵循FIFO（先进先出）原则。请参考此处：https://docs.oracle.com/javase/9/docs/api/java/util/Queue.html

队列通常按照FIFO（先进先出）方式排序元素，但并非必须如此。其中的例外是优先级队列，它根据提供的比较器或元素的自然顺序来排序元素。

PriorityQueue不遵循FIFO原则，这可能是您问题的原因。

- Srini Karthikeyan