为什么优先级队列不能像普通队列那样被包围？

Question

我知道，为了提高效率，排队使用了包绕法，以避免在删除元素的过程中一直将所有的东西向下移动。

但是，我不明白为什么优先级队列不能像普通队列那样绕来绕去。在我看来，优先级队列比队列具有更多类似于堆栈的行为，怎么可能呢？

Answer 1

最常见的优先级队列实现是二进制堆，它不会从包装中获益。您可以创建一个在循环缓冲区中实现的优先级队列，但是性能会受到影响。

重要的是要记住优先级队列是一种抽象的数据结构。它定义操作，但不定义实现。您可以将优先级队列实现为二进制堆、排序数组、未排序数组、二叉树、跳过列表、链接列表等。实现优先级队列的方法有很多种。

另一方面，二进制堆是优先级队列抽象数据类型的特定实现。

至于堆栈还是队列:实际上，堆栈和队列只是优先级队列的专门化。如果您认为时间是优先级，那么我们所称的队列( FIFO数据结构)实际上是一个优先级队列，其中最老的项是最高优先级。堆栈( LIFO数据结构)是一个优先级队列，其中最新的项是最高优先级。