数据结构笔记7队列（《大话数据结构》学习笔记）

【1】队列的定义

你们在用电脑时有没有经历过,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹 。就当你失去耐心,打算reset时。突然它像酒醒了 一样,把你刚才点击的所有操作全部都按顺序执行了一遍 。

这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。

再比如像移动、联通、电信等客服电话,客服人员与客户相比总是少数,在所有的客服人员都占线的情况下,客户会被要求等待,直到有某个客服人员空下来,才能让最先等待的客户接通电话。这里也是将所有当前拨打客服电话的客户进行了排队处理。

操作系统和客服系统中,都是应用了 一 种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。

队列 (queue) 是只允许在一端进行插入操作,而在另 一端进行删除操作的线性表 。

队列是一种先进先出的线性表,简称 FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。假设队列是 q= ( a1,a2,… , an) ,那 么a1就是队头元素,而 an 是队尾元素。这样我们就可以删除时 , 总是从 a1开始,而插人时,列在最后。这也比较符合我们通常生活中的习惯, 排在第一个的优先出列,最后来的当然排在队伍最后,

【2】队列的抽象数据类型

【3】循环队列

线性表有顺序存储和链式存储,栈是线性表,所以有这两种存储方式。同样,队列作为一种特殊的钱性表,也同样存在这两种存储方式。我们先来看队列的顺序存储结构 。

3.1队列顺序存储的不足
我们假设一个队列有 n 个元素,则顺序存储的队列需建立一个大于 n 的数组,并把队列的所有元素存储在数组的前 n 个单元,数组下标为 0 的一端即是队头。所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为O（1），如图：

与栈不同的是,队列元素的出列是在队头,即下标为 0 的位置,那也就意味着 ,队列中的所有元素都得向前移动,以保证队列的队头,也就是 下标为 0 的位置不为空,此时时间复杂度为O（n）如图：

可有时想想,为什么出队列时一定要全部移动呢,如果不去限制队列的元素必须存储在数组的前 n 个单元这一条件,出队的性能就会大大增加。也就是说,队头不需要一定在下标为 0 的位置 ,为了避免当 只 有一个元素时,队头和队尾重合使处理变得麻烦,所以引入两个指针, front 指针指向队头元素 , rear 指针指向队尾元素的下一个位置,这样当front等于 rear 时,此队列不是还剩一个元素,而是空队列 。

假设是长度为 5 的数组,初始状态,空队列如图的左图所示, front 与rear 指针均指向下标为 0 的位置 。 然后入队 a1、a2、a3、a4 , front 指针依然指向下标为 0 位置,而 rear 指针指向下标为 4 的位置,如图：

出队 a1、a2 ,则 front 指针指向下标为 2 的位置, rear 不变,如图的左图所示,再入队 a5,此时 front 指针不变, rear 指针移动到数组之外。

假设这个队列的总个数不超过 5 个,但目前如果接着人队的话,因数组末尾元素已经占用,再向后力日 ,就会产生数组越界的错误,可实际上,我们的队列在下标为 0 和 1 的地方还是空闲的 。 我们把这种现象叫做"假滥出 " 。

【4】循环队列定义

所以解决假溢出的办法就是后面满了 ,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列 。

刚才的例子继续, rear 可以改为指向下标为 0 的位置,这样就不会
造成指针指向不明的问题了。

接着入队6,将它放置于下标为 0 处, rear 指针指向下标为1处,如图左图所示。若再人队a7,则 rear 指针就与front 指针重合,同时指向下标为 2 的位置,如图

此时问题又出来了,我们刚才说,空队列时, fronr 等于rear,现在当队列满也是 front等于 rear ,那么如何判断此时的队列究竟是空还是满呢?

办法一是设置一个标志变量 flag , 当 frontrear ,且flag=0时为队列空,当frontrear,且 flag = 1 时为队列满。

办法二是当队列空时,条件就是 from= rear ,当队列满时,我们修改其条件,保留 一个元素空间。也就是说,队列满时,数组中还有一个空闲单元 。

例如图所示,我们就认为此队列已经满了

我们重点来讨论第二种方法,由于 rear 可能比 front 大,也可能比 front 小,所以尽管它们只相差一个位置时就是满的情况,但也可能是相差整整一 圈 。 所以若队列的最大尺寸为 QueueSize ,那么队列满的条件是 (rear+l ) % QueueSlze==front。 (取模 “%” 的目的就是为了整合 rear 与 front 大小为 一个问题)。

通用的计算队列长度公式为:

( rear- front + QueueSize) %QueueSize

循环队列的初始化代码如下:

循环队列求队列长度代码如下:


循环队列的入队列操作代码如下:

循环队列的出队列操作代码如下:

从这一段讲解,大家应该发现,单是顺序存储,若不是循环队列,算法的时间性能是不高的,但循环队列又面临着数组可能会溢出的问题,所以我们还需要研究一下不需要担心队列长度的链式存储结构。

【5】队列的链式存储结构及实现

队列的链式存储结构,其实就是线性表的单链表，只不过它只能尾进头出而已,我们把它简称为链队列 。

为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。

空 队列肘, front 和 rear 都指向头结点

链队列的结构为:

5.1 队列的链式存储结构一一入队操作
人队操作时,其实就是在链衰尾部插入结点.

5.2队列的链式存储结构一一出队操作

出队操作时,就是头结点的后继结点出队,将头结点的后继改为宫后面的结点,若链表除头结点外只剩一个元素时, 则需将 rear 指向头结点.

对于循环队列与链队列的比较,可以从两方面来考虑,从时间上,其实它们的基本操作都是常数时间,即都为 0(1) 的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销,如果入队出队频繁,则两者还是有细微差异。对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管官需要一个指针域, 会产生 一些空间上的开销,但也可以接受 。 所以在空间上,链队列更加灵活。

回顾：

栈 是限定仅在表尾进行插入和删除操作的线性表。

队列 ( queue) 是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

它们均可以用线性表的顺序存储结构来实现,但都存在着顺序存储的 一些弊端。对于栈来说,如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据,这就可以最大化地利用数组的空间。

对于队列来说,为了避免数组插入和删除时需要移动数据,于是就引入了循环队列 ,使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗,使得本来插入和删除是 O (n) 的时间复杂度变成了 O(1) 。