Day35-【13003】短文，什么是顺序队列，链式队列，链式队列如何结合空闲单元链表使用？

第二节队列概览

队列的定义及其基本操作

队列也是一 种特殊的线性表，其特殊性也体现在操作的位置上。

队列在日常生活中很常见，在数据结构中，它的含义与日常的通用意思是— 祥的。

例如，人们在日常生活中经常见到的排队，先到的人排在前面，后到的人应该排在队尾等候，排在最前面的人办完事情后离开。

这就是一 个队列，它具有优先的特性，即先来的人优先得到服务。这种先来先服务的特性称为先进先出。

• 栈具有后进先出的特性

定义3-2 队列是只能在表的一 端插入、在另一 端删除的线性表。

能进行插入的一 端称为队列尾，简称队尾；

能进行删除的— 端称为队列头，简称队头。

在队尾插入元素称为入队，

从队头删除元素称为出队。

仍然可以沿用线性表的方法来表示队列，队列Q可以表示为：

a0称为队头元素，

an-1称为队尾元素，

元素个数n称为队列长度。

当给定队列的入队序列后，仅能得到— 个出队序列，而且它是与入队序列完全相同的序列。

这是由队列先进先出的特性决定的。

队列的存储及实现

与线性表及栈一 样，队列也有两种实现方式，分别为顺序队列和链式队列。

(—)顺序队列

基本定义及出队操作时间复杂度

普通定义及时间复杂度

使用一 个一 维数组A （下标从0到n-1)来保存队列，数组的存储特点要求其中的元素必须紧凑存放在数组最前面的若干连续位置中，也就是不允许中间有空闲的位置。

假定队列中含有m (m≤n)个元素，

选择A[0]作为队头，

那么A[m-1]就是队尾。

当出队时，队头A[0]从数组中删除，此时要依次将后面的m-1个元素前移一 个位置。

在这种清况下，出队操作的时间复杂度是O (m )。

避免移动大量元素的队列定义

根据队列的定义，入队操作的位詈一 定在队尾，出队橾作的位詈一 定在队头。

无论采用哪种约定，数组下标为0的位置是放置队头元素还是队尾元素，其中必定有一 种橾作需要移动大量的元素，这显然得不偿失。

之所以出现这个问题，是因为约定了元素保存在数组从下标0开始的连续单元中 。如果去掉这个限制，则可以避免在入队或出队时必须要移动元素，从而部分地解决了这个问题。

当入队或出队时，不移动元素，导致的结果是将元素保存在数组中从某个位詈开始的若干连续单元中，开始位詈不再必须是下标0, 这看起来就像是数据占用的区域

整体地在数组中从前向后移动。

每次操作都可以有效地避免元素的移动。

但由于数据段的起始和终止位詈不断变化，故需要增加两个指示变量，用来标出这段区间。

可以使用变量front指示队头位置，

使用变量rear指示队尾位置。

习惯上，称front为队头指针，

rear为队尾指针。

与栈顶指针top类似，front和rear不是真正意义上的指针，它们都是整型值，表示的是数组下标。

通常，front指示的是队头元素所在的位詈，

rear指示的是队尾元素后面的空位詈。

按照惯例，还是将第一 个入队的元素保存在数组下标为0的位詈。

入队的新元素放詈到所有元素的后面。

在经过若干次入队、出队橾作后，含m个元素的队列的示意图如图3-9所示，

其中阴影部分表示队列中的元素实际占用的数组单元。

为避免前半段空闲单元浪费定义循环队列

当再进行若干次入队操作后，

rear会到达数组的末尾，即最后一 个下标位置，

如图3-10所示。若之后再进行入队操作，则会出现数组下标越界。但数组的前半段可能会因出队操作而有空闲的单元。

可以重复利用数组中前面的空闲单元来保存后续入队的元素，形成循环队列，如图3-11所示。

在每次元素出队后，front值加1，而rear值不变。

在将5和12出队后，front的值变为2。

再将后续的两个元素入队，rear到达数组最大的下标处，即6。

执行第二步操作后得到的队列如图3-13所示。

• 什么时候插入了25，和8进来

元素16入队后，保存在A[6]处，而rear的值变为0, 即绕回到数组的开头位置，然后9出队且7, 4依次入队，得到的队列如图3-14所示。

使用循环存储思想实现的队列称为循环队列， 一 般地，顺序队列均采用循环方式实现。

在循环队列中，入队操作会涉及队尾rear值的变化，rear= (rear+1)%n，出队橾作会涉及队头front值的变化，

front=(front+ 1)%n, 其中n是数组的大小。

可以把这个数组想象成一 个首尾相接的圆环，A[n-1]的后面是A[0]。

＂循环” 一 词的含义正是如此。

在循环队列中，因为元素保存在数组中，所以入队时还需要判定数组是不是已满，这个“满” 是真的满，即数组中已经没有空闲单元来保存元素了，而不是判定数组下标是否越界。

同样，出队时要考虑队列是否为空。

所以，需要判定这种清况下数组的满或空。

循环队列可嫩的问题

另外，假设队列中只含有一 个元素，如图3-15所示。

出队一 个元素，front加1，则此时rear== front也成立。

条件rear== front也代表空队列。

若使用循环队列，就会存在这样的问题。

1、可以使用如下解决方法：让数组中始终剩余至少一 个空位置。

当数组中仅有— 个空位置 时，就认为已经达到队列的最大长度了，队列已满。

在这样规定后，图3-14所示的队列就是满队列了。

在数组中唯一 的空闲位置介于下标0和下标n-2之间时，队列的清况类似于图3-14的形式，此时， front= rear+ 1。

当唯一 的空闲位詈在下标n-1时，也代表队列满，如图3-16所示，此时，rear= front+n-1。

这两种情况都满足(rear+1)%n==front, 因此这个表达式是队列满的判定条件。

2、如果不想浪费队列中的空间，则可以增加一 个变量来帮助区分rear==front时，队列是空还是满。

例如，

• 增加— 个标记flag来表示入队或出队操作，不妨设入队是1, 出队是0。

如果flag是1，满足rear= = front时意味着队列已满；

如果flag是0, 则满足rear= = front时意味着队列为空。

• 还可以直接使用一 个整型变量len来记录队列的长度。

len初值为0,当有元素入队时，len增1,

出队时，len减1。

在需要判定队列的空或满状态时，直接使用len的值即可。

这两种方法都是在队列之外再增加一 个变量，每次进行入队或出队操作时，需要同步进行修改，以保证数据的— 致性。

初始时，front和rear的值分别是什么呢？

空队列满足的条件是rear== front。

第一 个入队的元素放在数组的第一 个位詈，所以初始时，front= 0且rear= 0。

(二)链式队列

基本定义

与栈的处理清况— 祥，当不能确定队列中同时保存的元素个数的上限时，可以采用链式存储方式，

即 使用一 个单链表保存队列，这样的队列称为链式队列。

链式队列采用带头指针及尾指针的单链表作为队列的存储结构。

单链表的头指针可以当作队头，指针front,

尾指针可以当作队尾，指针rear。

因为单链表中表尾元素的后面没有结点，故队尾指针rear指向队尾元素。

因为队列中的操作可以通过front和rear来完成，

入队相当于在链表表尾的插入，

出队相当于在链表表头的删除，

所以单链表中的头结点不是必需的。

当然，也可以与单链表的表示一 致，在链式队列的最前面加上头结点。

实现基本操作

初始化操作

链式队列的基本操作要实现的基本功能与循环队列的基本操作是— 样的，但因为两种队列的存储方式不同，故实现方式也不同。

在链式队列中，因为不需要头结点， 所以初始化橾作中，只给队头指针和队尾指针分别赋初值NULL。

清空队列操作

队列清空橾作需要做两件事，

首先将队列中的所有结点从队列中删除， 并释放所占用的空间，

其次将队列的头指针和尾指针赋值为NULL。

判断空

入队，出队，及操作的时间复杂度

以单链表保存的队列是链式队列，通常需要两个指针分别指向队头结点和队尾结点。

• 入队时，新元素插入在队尾，队尾指针—定要修改，让它指向这个新元素。通常队头指针是不需要修改的。

​ 但当向空队列中插入一 个新元素时，队头指针也需要修改。

• 在链式队列进行出队橾作时，通常也是如此，大部分情况下，仅需要修改队头指针。

​ 但当队列为空时，除需要修改队头指针以外，还需要修改队尾指针。

结合空闲单元链表使用

在采用链式方式实现队列时，也可以像单链表那样，配合使用一 个空闲单元链表，使得入队、出队时尽量少地调用malloc函数及free函数。

在单链表中，数据链表与空闲单元链表是两个独立的链表。

在链式队列中，可以将这两个链表合在一 起，形成— 个圆环，即使用— 个循环链表来表示链式队列及对应的空闲单元链表，如图3-18所示。

在这个循环链表中，结点分为两部分， 一 部分结点用来保存实际数据，另一 部分结点是空闲结点。

初始状态

使用front指向保存队列当前首元素的结点，使用freeN指向空闲单元链表的首结点，而且队尾指针rear是可选的。

初始时建立含一 个结点的链式队列，该结点作为链式队列与空闲单元链表之间的分界，且指针front和指针freeN都指向这个结点，如图3-19所示。

此时，队列和空闲单元链表均为空。

入队、出队

• 在元素入队时，如果空闲单元链表不空，则新元素保存在freeN指向的结点中，然后freeN转移指向下一个结点。

​ 如果空闲单元链表为空，则将新元素保存在freeN指向的结点中，同时分配— 个新结点，并将它插入在freeN指向结点的后面，且让freeN指向该新结点。

​ 空闲单元链表为空的条件是freeN->next==front。

• 在元素出队时，如果队列为空，则front指向的结点中保存的是要出队的元素，然后front转移指向下一个结点。

​ 如果队列为空，则不能出队。

​ 队列为空的条件是freeN==front。

例如，当首次向链式队列中插入一 个新元素时，得到的链式队列如图3-20所示。