编程概念：队列

队列是一种在计算中广泛使用的先进先出 (FIFO) 抽象数据类型。队列的用途包括任何需要按照调用顺序执行的操作，但计算机无法跟上速度。例如

• 键盘缓冲区 - 您希望字母按照您按下的顺序显示在屏幕上。您可能会注意到，当您的计算机很忙时，您按下的键不会立即显示在屏幕上，而要稍等片刻。当它们显示出来时，它们会按照您按下的顺序显示。
• 打印机队列 - 您希望打印作业按照您发送的顺序完成，即第 1 页、第 2 页、第 3 页、第 4 页等。当您共享打印机时，几个人可能会向打印机发送打印作业，而打印机无法立即打印，因此您需要等待一段时间，但输出的项目将按照您发送的顺序进行。

有几种不同类型的队列，如下所述

线性

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

线性 FIFO 队列的表示

现实生活中的例子是在超市排队结账。第一个进入队列的人是第一个被服务的人。如果你最后一个加入队列，你将是最后一个被服务的人（不要插队！）。然而，有一个区别，在超市队列中，一旦第一个被服务，其余的队列就会向前移动，使之前第二个人现在成为第一个，这在计算机中是可能的，但在处理方面非常昂贵。您将看到的线性队列会“爬”过内存，吞噬它遇到的所有东西。

线性队列的最基本实现将遍历其分配的内存，而不会重用内存。前端和后端指针只能向前移动，迟早会到达分配内存的末尾 - 在这一点上，无法再向队列添加更多项目。看看这个例子以及存储队列前端的两个指针（FrontPtr）和下一个空闲内存位置（NextFree）的值。

状态 1	状态 2	状态 3	状态 4	状态 5	状态 6
起始状态	H 加入队列	开始被服务	J 加入队列	开始被服务	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 Output = D 注意没有数据被 '删除'，但 指针已更改	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 Output = G	1 2 3 4 5 6 D G A H J P FrontPtr = 3 NextFree = 7 即使 3 之前的插槽 不再需要，但 无法添加更多数据，因为 NextFree 已超过 最后一个插槽

一个更好的实现将通过每次从前端删除一个项目时将每个项目向左移动一个来重用内存。但是，如果队列中有许多项目，这可能会变得非常慢。见下文（注意我们不再需要前端指针，因为项目 1 始终是前端）

状态 1	状态 2	状态 3	状态 4	状态 5	状态 6
起始状态	H 加入队列	开始被服务	J 加入队列	开始被服务	P 加入队列
1 2 3 4 5 D G A NextFree = 4	1 2 3 4 5 D G A H NextFree = 5	1 2 3 4 5 G A H NextFree = 4 Output = D D 被删除，其他 项目被移动 到左边	1 2 3 4 5 G A H J NextFree = 5	1 2 3 4 5 A H J NextFree = 4 Output = G	1 2 3 4 5 A H J P NextFree = 5

易于实现，代码简单

然而

从队列前端删除项目可能会很慢

循环

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

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

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

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

图表	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 獾 雪貂 黄鼠狼 如果它是循环队列？ 答案 1 2 3 4 5 熊 雪貂 黄鼠狼 猴子 蛇 StartPtr = 2 EndPtr = 1 如果它是线性队列？ 答案 这将失败，因为队列中没有更多空间了！ 描述队列的功能 答案 先进先出数据类型 说出在计算机中使用队列的两个用途。 答案 键盘缓冲区 打印机队列