代码之家 › 专栏 › 技术社区 › Alex Blasco

为什么优先级队列不能像普通队列一样环绕?

abstract-data-type priority-queue queue stack data-structures

0

Alex Blasco · 技术社区 · 7 年前

我知道为了提高效率, Queues 使用 wrap around method ,以避免在删除元素时将所有内容下移。

但是,我不明白为什么 Priority Queues 不能像普通的队列那样绕来绕去。在我看来,优先级队列的行为与 Stack 比起排队,怎么可能呢?

1 回复 | 直到 7 年前

1

Jim Mischel 7 年前

最常见的优先级队列实现是 binary heap 这不会从包装中受益。您可以创建一个在循环缓冲区中实现的优先级队列,但是性能会受到影响。

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

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

至于栈vs队列:实际上,栈和队列只是优先级队列的专门化。如果您将时间视为优先级,那么我们称之为队列(FIFO数据结构)实际上是优先级队列,其中最旧的项是最高优先级。堆栈(后进先出数据结构)是一个优先级队列,其中最新的项是最高优先级。