3.2 队列

与栈相似，队列也是一种操作受限制的线性表。队列有与栈相似的基本操作，但在特性和应用场景上却有很大不同。本节除讨论队列的基本概念、定义及基本操作外，也会给出常见的应用示例。

3.2.1 队列的基本概念

和栈相反，队列是一种先进先出的线性表，其插入操作只能在表的尾部进行，删除操作只能在表头进行。在队列中允许进行插入操作的一端称为队尾，允许进行删除操作的另一端称为队首。在队列{a₀,a₁,…,a_n-1}中，a₀称为队首元素，a_n-1称为队尾元素。通常，队列的插入操作叫入队，队列的删除操作叫出队。没有数据元素的队列称为空队列。

3.2.2 队列的抽象数据类型描述

队列中的数据元素和数据间的逻辑关系与线性表相同，是由n个具有相同数据类型的数据元素构成的有限序列，队列的抽象数据类型的Python语言描述如下。

队列的Python抽象类包含了它的主要基本操作，如果要使用这个接口，还需要具体的类来实现。Python抽象类的实现方法主要有以下两种。

1）基于顺序存储的实现，为顺序队列。

2）基于链式存储的实现，为链队列。

3.2.3 顺序队列

1.顺序队列类的描述及实现

顺序队列的存储结构与顺序栈类似，可用数组实现。因为入队和出队操作分别在队尾和队首进行，所以增加变量front来指示队首元素的位置，rear指示队尾元素的下一个存储单元位置。顺序队列进行入队操作后的状态变化如图3-8所示，进行出队操作后的状态变化如图3-8所示。

顺序队列类的Python语言描述如下。

2.循环顺序队列类的描述及实现

分析发现，顺序队列的多次入队和出队操作会造成有存储空间却不能进行入队操作的“假溢出”现象，如图3-9所示。顺序队列会出现“假溢出”现象是因为顺序队列的存储单元没有重复使用机制。为了解决顺序队列因数组下标越界而引起的“溢出”问题，可将顺序序列的首尾相连，形成循环顺序队列。循环顺序队列进行入队和出队操作后的状态变化如图3-10所示。

循环顺序队列中又有新的问题产生——队空和队满的判定条件都变为front==rear。为了解决这一问题，可以少利用一个存储单元，使队列最多存放maxSize-1个数据元素，队空的判定条件为front==rear，队满的判定条件为front=(rear+1)%maxSize。

循环顺序队列类和顺序队列类的Python语言描述相似，仅是指示变量front和rear的修改以及队满的判定条件发生了变化。

循环顺序队列的Python语言描述如下。

【例3.5】 队列长度计算。

假定用于顺序存储一个队列的数组长度为N，队首和队尾指针分别为front和rear，写出求此队列长度（即所含元素个数）的公式。

【解】 当rear大于或等于front时，队列长度为rear-front，也可以表示为(rear-front+N)%N；当rear小于front时，队列被分成两个部分，前部分在数组尾部，其元素个数为N-1-front，后部分在数组首部，其元素个数为rear+1，两者相加为rear-front+N。综上所述，在任何情况下队列长度的计算公式都为(rear-front+N)%N。

【例3.6】 在执行操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后队首元素和队尾元素分别是什么？EnQueue(k)表示整数k入队，DeQueue表示队首元素出队。

【解】上述操作的执行过程如图3-11所示。

所以队首元素为5，队尾元素为9。

3.2.4 链队列

用链表表示的队列简称为链队列。由于入队和出队分别在队列的队尾和队首进行，不存在在队列的任意位置进行插入和删除的情况，所以不需要设置头结点，只需要将指针front和rear分别指向队首结点和队尾结点，把每个结点的指针域指向其后继结点即可。

图3-12所示为链队列进行入队操作后的状态变化。

图3-13所示为链队列进行出队操作后的状态变化。

通过利用Node类，链队列的Python语言描述如下。

3.2.5 优先级队列

有些应用中的排队等待问题仅按照“先来先服务”原则不能满足要求，还需要将任务的重要程度作为排队的依据。例如操作系统中的进程调度管理，每个进程都有一个优先级值表示进程的紧急程度，优先级高的进程先执行，同级进程按照先进先出原则排队等待，因此操作系统需要使用优先级队列来管理和调度进程。又比如打印机的输出任务队列，对于先后到达的打印几百页和几页的任务，将优先完成页数较少的任务，从而使得任务的总等待时间最小。

优先级队列是在普通队列基础之上将队列中的数据元素按照关键字的值进行了有序排列。优先级队列在队首进行删除操作，但为了保证队列的优先级顺序，插入操作不一定在队尾进行，而是按照优先级插入队列的合适位置。

和其他数据结构类似，优先级队列也可以采用顺序和链式两种存储结构。但为了快速地访问优先级高的元素以及快速地插入数据元素，通常使用链式存储结构。

1.优先级队列结点类的描述

优先级队列有这样的特征：允许元素以任意次序进入队列内，但在取出元素时按照优先级大小取出。故而在设计优先级队列的结点类时增加了“优先级”域，在出队时通过比较各结点的优先级大小来决定出队顺序。

2.优先级队列类的描述及实现

注意：在此优先级队列中，数据元素的优先级依据优先数的大小进行判定，即优先数越小优先级越大。

3.优先级队列类的应用

【例3.7】 利用优先级队列模拟操作系统的进程管理问题，要求优先级高的进程先获得CPU，优先级相同的进程先到的先获得CPU。假设操作系统中的进程由进程号和进程优先级两部分组成。4个进程的进程号和优先级分别为1,2,3,4和20,30,10,50。约定优先级数越大，优先级越高。

【解】 操作系统中的进程会以任意顺序进入等待队列，等待获取CPU的使用权。而依据题目描述，优先级高的进程先获得CPU，优先级相同的进程先到的先获得CPU，符合优先级队列的特性。

【实现代码】