编程概念：队列

一个 队列 是一个先进先出 (FIFO) 抽象数据类型，在计算中被广泛使用。队列的使用涉及任何你想让事情按照它们被调用的顺序发生，但计算机无法跟上速度的情况。例如

• 键盘缓冲区 - 你希望字母按照你按下它们的顺序出现在屏幕上。你可能会注意到，当你的计算机很忙时，你按下的键不会立即出现在屏幕上，而是要过一会儿才会出现。当它们出现时，它们会按照你按下的顺序出现。
• 打印队列 - 你希望打印作业按照你发送它们的顺序完成，即第 1 页，第 2 页，第 3 页，第 4 页等。当你在共享打印机时，几个人可能会发送打印作业到打印机，而打印机无法立即打印东西，因此你必须等待一会儿，但输出的项目将按照你发送它们的顺序进行。

有几种不同类型的队列，例如下面描述的那些

线性

在这种队列形式中，元素能够在队列的一端加入，并能够从队列的另一端退出。先进先出 (FIFO)。

线性 FIFO 队列的表示

现实生活中一个例子是超市收银台的排队。第一个进入队列的人是第一个被服务的。如果你最后加入队列，你将被最后服务（没有插队！）。但是，有一个区别，在超市队列中，一旦第一个被服务，队列的其余部分就会向前移动，使先前排在第二位的人现在排在第一位，这在计算机中是可能的，但在处理方面成本很高。你即将看到的线性队列会在内存中“爬行”，吞噬它遇到的所有东西。

线性队列不断地在内存中工作，它不重复使用内存。因此，如果大量的项目被添加到列表中并从列表中移除，这意味着列表将会变得非常大，而不会包含太多数据。它不是一个非常有效的解决方案，会消耗大量的内存。看看这个例子，以及存储队列前端（FrontPtr）和下一个空闲内存位置（NextFree）的两个指针的值。

状态 1	状态 2	状态 3	状态 4	状态 5	状态 6
起始状态	H 加入队列	Start 被服务	J 加入队列	Start 被服务	P 加入队列
1 2 3 4 5 D G A FrontPtr = 1 NextFree = 4	1 2 3 4 5 D G A H FrontPtr = 1 NextFree = 5	1 2 3 4 5 D G A H FrontPtr = 2 NextFree = 5 请注意，没有数据 被“删除”，但 指针已更改	1 2 3 4 5 D G A H J FrontPtr = 2 NextFree = 6	1 2 3 4 5 D G A H J FrontPtr = 3 NextFree = 6	1 2 3 4 5 6 D G A H J P FrontPtr = 3 NextFree = 7

实现速度快，代码简单

然而

消耗大量的内存，可能会覆盖重要的内存位置

循环

与线性队列不同，循环队列允许重复使用内存

通常，循环缓冲区需要三个 指针

• 一个指向内存中的实际缓冲区
• 一个指向有效数据的开头
• 一个指向有效数据的结尾

以下示例显示了一个部分填充的固定长度缓冲区，以及它如何处理队列中的添加和删除。特别注意指针。

图表	StartPtr	EndPtr
	3	5
数据被指定为在 StartPtr 和 EndPtr 之间
	3	6
向队列添加另一个元素会将 EndPtr 向上移动一个
	4	6
从队列前端删除一个元素是通过将 StartPtr 增加一个来实现的
	4	7
向队列添加另一个元素会将 EndPtr 向上移动一个，现在它位于缓冲区的末尾
	4	1
向队列添加另一个元素会使 EndPtr 循环到缓冲区开头的空闲空间
	4	2
向队列添加另一个元素会将 EndPtr 向上移动一个，现在它正在接近 StartPtr
	4	3
向队列添加另一个元素会将 EndPtr 向上移动一个，现在它正在接近 StartPtr。 如果我们尝试向循环队列添加另一个元素，我们将无法做到，除非首先从队列前端删除某些东西

循环队列在计算机科学中非常常见，它们被用来存储东西，它们具有以下优点

它们重复使用内存空间，这意味着它们不会覆盖数据或用完内存（在一定范围内）

以及缺点

除了数据之外，还要存储指针，占用的空间比线性队列更大

受缓冲区（数组）中可用数据量的限制

优先级

这是基于队列中元素的优先级顺序。换句话说，这种类型的队列中的每个元素都附加了不同的优先级级别；例如，高优先级或低优先级。

急诊室 是优先级队列的一个例子

现实生活中一个例子是急诊室候诊室，摔倒的人可能比头破血流的人优先级低，因此即使头部受伤的病人后来进来，他们也可能插队。

状态 1	状态 2	状态 3
1. 胳膊骨折 2. 膝盖擦伤	1. 心脏病发作 2. 胳膊骨折 3. 膝盖擦伤	1. 心脏病发作 2. 严重脑震荡 3. 胳膊骨折 4. 膝盖擦伤
初始队列	心脏病发作最高优先级，插队	严重脑震荡比心脏病发作不重要，因此移动到第二位

在计算机中，我们使用优先级队列来处理进程的执行。每个进程都将附加一个优先级，当更重要的进程需要处理器时，它们会跳过不太重要的进程，以获得处理器的关注。例如

进程	优先级
网络浏览器	正常
媒体播放器	低于正常
操作系统安全	高
计划的病毒扫描程序	低
打印队列	低
文字处理器	正常

扩展调度算法 我们有几种方法可以用来处理处理器调度，每种方法都有自己的优缺点 调度算法 CPU 利用率 吞吐量 周转时间 响应时间 先进先出 低 低 高 低 最短作业优先 中等 高 中等 中等 基于优先级的调度 中等 低 高 高 循环调度 高 中等 中等 高 多级队列调度 高 高 中等 中等

练习：队列 为什么使用循环队列比线性队列更好？ 答案 循环队列使用固定数量的内存，并在遍历队列时重用内存。线性队列不重用内存，可能会浪费内存。 命名实现循环队列中使用的三个指针 答案 一个指向内存中的实际缓冲区 一个指向有效数据的开始（StartPtr） 一个指向有效数据的结束（EndPtr） 当优先级更高的任务需要处理器注意时，优先级队列中会发生什么？ 答案 较低优先级的任务会被排队，而较高优先级的任务会被分配到处理器。 当 Monkey 和 Snake 被添加，第一个项目被移除，然后 Bear 被添加到以下队列时，指针的值是多少？ 1 2 3 4 5 Badger Ferret Weasel 如果是循环队列？ 答案 1 2 3 4 5 Bear Ferret Weasel Monkey Snake StartPtr = 2 EndPtr = 1 如果是线性队列？ 答案 这会导致错误，因为队列中没有剩余空间！ 描述队列的功能 答案 先进先出的数据类型 命名在计算机中使用队列的两个用途 答案 键盘缓冲区 打印机队列