都是队列，优先级队列吗？如果不是，有什么区别？

Question

刚刚开始我的数据结构和算法学习之旅，我就被这样一个事实所困扰：到处都有关于这种东西的信息，每个数据结构都有不同的昵称。但通俗地说，所有队列实际上都是优先级队列，优先级位正是使它们如此特别的原因？

我试过谷歌搜索所有队列优先队列，我被推荐到堆栈溢出的大量信息蜂巢思维。

Answer 1

答案是Yes和No。 理论上所有队列都是优先级队列，是的。但是如果优先级是插入顺序（又名先进先出），那么它可以用其他专门优化的数据结构来实现，这可能会更快。

通用优先级队列需要某种复杂的“堆”类型的数据结构，

std::queue

或

std::heap

处理。

但是，插入顺序队列可以通过“类似列表”的数据结构来实现，这通常快far，例如

std::list

和

std::dequeue

。因此，尽管它们是相同的通用概念，但具体实现通常通常使用完全不相关的数据结构。 （理论上也可以使用

std::vector

，但要避免 O(n)

pop()

需要一些工作，所以通常人们不使用它。）

你在其他地方也看到了这一点。通俗地说，“列表”是一个笼统的概念。但是C++把这个概念叫做“SequenceContainer”，然后很容易混淆地将他们的SequenceContainer链表数据结构命名为

std::list

。但通俗地说，

std::vector

和

std::deque

和

std::array

也是列表，尽管它们是完全不相关的数据结构。

Answer 2

“队列”既是一组通用数据结构的名称，也是该组中特定数据结构的名称。

作为一个一般的群体，你可以把队列想象成排队的人或物品：一系列有序的东西，顺序决定了先取出哪个物品。

组内的特定数据结构因维护顺序的方式而异。仅通过“队列”的特定数据结构将所有新项目添加到队列的一端，并在另一端提取它们。它是“先进先出”（FIFO），就像人们在博物馆排队或杂货在超市的传送带上排队一样。

按“优先队列”排序的特定数据结构按项目的“价值”排序，无论这意味着什么。例如，我可能会优先排队，这样我总是可以先呼叫最高的人。实现的不同之处在于整个队列是否按此值排序，或者只是巧妙地安排以便总是很容易找到最大或最小的项目。它们分别是最大堆和最小堆。

总而言之，严格来说并非所有队列都是优先队列，尽管 Mooing Duck 是正确的，所有队列都以某种方式排序。