3.6 列的顺序存储结构★2◎4
3.6 队列的顺序存储结构★2◎4
作为线性表的一种,可以使用数组来实现队列的顺序存储。
1.队列顺序存储结构表示
如下定义了一个数据元素为Elemtype的顺序存储队列的例子:
其中,采用整型front来描述队列头指针,它指向队列中第一个元素,即下一个出队列的元素;整型rear描述队列尾指针,它指向下一个入队列元素的存储位置,如图3-6所示。
如图3-6(c)所示,rear指针已经到达最上端,此时队列“已经用完”,不能再插入数据了。这就是顺序队列的“假溢出”现象,其实在队列的下端还有相当数量的存储空间可供使用。因此,队列的顺序存储结构一般采用“循环队列”的形式:将数组空间看成一个环状,当rear或front到达数组的一端时,让其自动回到数组的另一端,如图3-6(d)所示。
2.循环队列
循环队列仍然使用顺序存储结构,只不过每次进行入队列操作和出队列操作时,指针front和rear不是简单的自加,而是需要判断是否过界(即不能超过QMAXSIZE),一旦过界,就需要重新从0开始。循环队列的示意图如图3-7所示。
3.有关循环队列的判断
如果用C语言来实现循环队列时,则:
队列空的条件是:“front == rear”,如图3-7(b)所示。
队列满的条件也是:“front==rear”,如图3-7(d)所示。
因此,队列满和队列空的条件一模一样,为了能够区分开,有两种折中方案:
(1)记载队列元素数量
在结构QUEUE中增加一个变量count记载队列中的元素数量,初始值为0,每当执行入队列操作时“count++”,每当执行出队列操作时“count–”。如果“front==rear”条件成立,则进一步判断count的取值,当count取值为0时表示队列空,否则队列满。
(2)少用一个元素空间
在循环队列中增加一个不使用的存储空间,当队列中存入了“QMAXSIZE-1”个元素时,即认为循环队列满,不再进行入队列操作,如图3-7(c)所示,此时算式:
成立。
以上两种方法在各种操作下的对比如表3-5所示。
表3-5 两种循环队列实现方法对比表
操 作 | 记载队列元素数量 | 少用一个元素空间 |
队列初始化 | front=0;rear=0;count=0 | front=0;rear=0; |
队列元素数 | count | (rear-front+QMAXSIZE)%QMAXSIZE |
队列空判断 | front==rear && count==0 | front==rear |
队列满判断 | front==rear && count!=0 | ((rear+1) % QMAXSIZE)== front |
入队列时指针操作 | rear=(rear+1) % QMAXSIZE; count++; | rear=(rear+1) % QMAXSIZE; |
出队列时指针操作 | front=(front+1) % QMAXSIZE; count–; | front=(front+1) % QMAXSIZE; |
空间复杂度 | 增加一个变量 | 降低了一个单位的存储能力 |
4.入队列操作
数据元素入队列操作过程可分为三个步骤:
①判断队列未满。
②将数组元素Elem[rear]赋值为入队列元素。
③移动队列指针。
以方法2为例,需将队列尾指针增加1,如果指针越界(超过QMAXSIZE)则指针赋值为0。这个操作其实可以使用“取模”运算快速实现,代码为:
以下代码实现队列Q的入队列操作:
5.出队列操作
数据元素的出队列操作过程可分为三个步骤:
① 判断队列未空。
②返回数组元素Elem[front]。
③移动队列指针。
以方法2为例,需将队列头指针指向队列的下一个数据元素,即front取值加1,如果指针越界(超过QMAXSIZE),则指针赋值为0。本次也可以使用“取模”运算,代码为:
以下代码实现队列S的出队列操作:
6.循环队列的特点
(1)由于只在顺序线性表头执行删除操作,在顺序线性表尾执行插入操作,不用数据移动,因此其算法的时间复杂度为常数。
(2)不能随意增加队列的最大存储空间,这样容易造成队列满。
(3)需要一次性分配所需的存储空间,当此队列未达到最大数据元素数时浪费了存储空间。
因此循环队列适用于数据元素总数固定而且数量不大的应用中,比如在DOS下接收键盘输入的缓冲区就是一个循环链表。
3.6 列的顺序存储结构★2◎4