logo标签列表

优先队列 VS 队列

data-structuresqueuepriority-queue
5

优先队列是一种队列数据结构。它不遵循FIFO原则，因此它应该被命名为优先级数组或优先级链表，主要是因为优先队列不像FIFO队列那样遵循一种模式。

3个回答
6
在优先队列中，具有高优先级的元素先于低优先级元素服务。如果两个元素具有相同的优先级，则按照它们在队列中的顺序进行服务。我认为这将回答你的问题。
3
如果你看一下最常用的实现，优先队列基本上就是堆——它们根据程序员定义的优先级以特定的方式排列——在一个简单的例子中，按整数的升序或降序排列。
把优先队列想象成一个队列，你检索元素的方式不是基于添加元素的时间顺序，而是基于它们彼此之间的比较。这种比较可以在教科书样例中简单地按升序或降序排列。你可以从另一个StackOverflow答案的类比中理解ADT:
“你在医院工作，病人陆续来到。只有一位医生在岗。第一个男人走进来——他立即得到服务。接下来，一个感冒的男人来了，需要帮助。你把他加入队列，他排队等待医生可用。接下来，一个头上插着斧子的男人走进门。他被分配了更高的优先级，因为他是更高的医疗责任。所以感冒的男人在队伍中被挤下了。接下来，有人出现呼吸问题。所以，感冒的男人再次降低了优先级。这在现实世界中被称为触发——但在这种情况下，这是一条医疗线。”
在代码中实现这个功能将使用一个优先队列和一个工作线程（医生）来处理可消耗/工作单元（病人）。
在真实的场景中，你可能有等待CPU处理的进程。
阅读：何时应该使用优先队列？
0
在队列中，元素等待的时间越长，自然排序就越公平。当你排队等待某些事情时，先来先服务。
然而，有时候一些特殊的元素可能会表明它们应该比其他等待时间更长的元素更早地得到服务。例如，我们并不总是按照接收邮件的顺序阅读邮件，但通常会跳过朋友发来的新闻简报或“有趣”的笑话，先阅读与工作相关的信息。
同样，在设计应用程序或测试应用程序时，如果存在一些错误，这些错误将根据其严重程度进行优先处理。首先，新的错误会不断被发现，因此新的项目将被添加到列表中。假设发现了一个恶性认证错误——你需要在昨天之前解决它！此外，错误的优先级可能随着时间的推移而改变。例如，你的CEO可能决定你要争取使用X浏览器的市场份额，并且下周五你将推出一个重大功能，因此你真的需要在几天内解决底部的那个错误。

优先队列在需要按照特定顺序消耗动态变化列表中的元素时非常有用（例如要在CPU上运行的任务列表），因此我们可以随时获取下一个元素（根据某种标准），将其从列表中删除，并且通常不必担心其他元素的修复。

这就是优先队列背后的思想：它们的行为类似于常规的普通队列，只是队列的前端基于某种优先级进行动态确定。引入优先级所引起的差异是深刻的，足以值得一种特殊的数据结构。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接