3.10.什么是队列
Last updated
Last updated
队列是项的有序结合,其中添加新项的一端称为队尾,移除项的一端称为队首。当一个元素从队尾进入队列时,一直向队首移动,直到它成为下一个需要移除的元素为止。
最近添加的元素必须在队尾等待。集合中存活时间最长的元素在队首,这种排序成为 FIFO,先进先出,也被成为先到先得。
队列的最简单的例子是我们平时不时会参与的列。排队等待电影,在杂货店的收营台等待,在自助餐厅排队等待(这样我们可以弹出托盘栈)。行为良好的线或队列是有限制的,因为它只有一条路,只有一条出路。不能插队,也不能离开。你只有等待了一定的时间才能到前面。Figure 1 展示了一个简单的 Python 对象队列。
Figure 1
计算机科学也有常见的队列示例。我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时,他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个,你必须等待你前面的所有其他任务打印。我们将在后面更详细地探讨这个有趣的例子。
除了打印队列,操作系统使用多个不同的队列来控制计算机内的进程。下一步做什么的调度通常基于尽可能快地执行程序和尽可能多的服务用户的排队算法。此外,当我们敲击键盘时,有时屏幕上出现的字符会延迟。这是由于计算机在那一刻做其他工作。按键的内容被放置在类似队列的缓冲器中,使得它们最终可以以正确的顺序显示在屏幕上。