用循环数组实现队列
《用循环数组实现队列》由会员分享,可在线阅读,更多相关《用循环数组实现队列(10页珍藏版)》请在装配图网上搜索。
1、用循环数组实现队列我们可以将队列当作一般的表用数组加以实现,但这样做的效果并不好。尽管我们可 以用一个游标last来指示队尾,使得Enqueue运算可在0(1)时间内完成,但是在执行 Dequeue时,为了删除队头元素,必须将数组中其他所有元素都向前移动一个位置。这样, 当队列中有n个元素时,执行Dequeue就需要0(n)时间。为了提高运算的效率,我们用另一种方法来表达数组中各单元的位置关系。设想数组 Q1.MaxLength中的单元不是排成一行,而是围成一个圆环,即Q1接在QMaxLength 的后面。这种意义下的数组称为循环数组,如图 2 所示。用循环数组实现队列时,我们将队列中从队头到
2、队尾的元素按顺时针方向存放在循环 数组中一段连续的单元中。当需要将新元素入队时,可将队尾游标Q.rear按顺时针方向移 一位,并在新的队尾游标指示的单元中存入新元素。出队操作也很简单,只要将队头游标 Q.fr ont依顺时针方向移一位即可。容易看出,用循环数组来实现队列可以在0(1)时间内完 成Enqueue和Dequeue运算。执行一系列的入队与出队运算,将使整个队列在循环数组 中按顺时针方向移动。在图2中,我们直接用队头游标Q.front指向队头元素所在的单元,用队尾游标Q.rear 指向队尾元素所在的单元。另外,我们也可以用队头游标Q.fro nt指向队头元素所在单元的 前一个单元,或者
3、用队尾游标Q.rear指向队尾元素所在单元的下一个单元的方法来表示队 列在循环数组中的位置,如图3所示。图 3 循环数组中的队头与队尾游标在循环数组中,不论用哪一种方式来指示队头与队尾元素,我们都要解决一个细节问 题,即如何表示满队列和空队列。图4给出一个例子,MaxLength=6,队列中已有3个元 素。我们用上述3种方法来指示队头和队尾元素,分别如图4(a)、(b)和(c)所示。(a)(b)(c)图 4 循环数组中的队列现在,有3个元素a4,a5,a6相继入队,使队列呈满的状态,则如图5相应的(a),(b)和 (c)所示。(a)图5队列满的情形如果在图4中,3个元素a1,a2,a3相继出队
4、,使队列呈空的状态,则如图6相应的(a),(b) 和(c)所示。(a)(b)Q. front Q- rear(c)图 6 队列空的情形比较图5和图6 我们看到,不论采用哪一种方式指示队头和队尾元素,都需要附加说 明或约定才能区分满队列和空队列。通常有两种处理方法来解决这个问题。其一是另设一个布尔量来注明队列是空还是满 二是约定当循环数组中元素个数达到M axLe ngth-1时队列为“满”,使得队列满和队列空时的 队头和队尾游标的相对位置不同,从而满队列和空队列得以区分。例如,在图4 中,当元 素a4和a5相继入队后,就便队列呈“满”的状态,如图7所示。比较图7和图6,显然只要 测试头和队尾游
5、标的相对位置便可区分出满队列和空队列。(a)(b)为确定起见,这里采用图2的方式定义Q.front 和 Q.rear,另采用上述的第二种处理法区分满队列和空队列。这样,队列的类型 QueueType 说明为:typeTPositi on=in teger;QueueType = recordEleme nts:array1.MaxLe ngth of Eleme ntType;fron t,rear:TPositi on;en d;那么,在用循环数组实现的队列中,队列的5种基本运算可实现如下。其中人表示空 元素,要根据不同的元素类型来确定。函数 Front(Q)功能这是一个函数,函数值返回队列
6、Q的队头元素。用一般的表运算可将Front(Q) 表示为Retrieve(First(Q),Q)。如果队列为空则返回空元素人。实现Fun cti on Fron t(var Q:QueueType):Eleme ntType;beginif Empty(Q) then return(A)else retur n( Q.Eleme ntsQ.fro nt);en d;说明显然复杂性显然为0。函数 Enqueue(x,Q)功能将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。也可用二般 的表运算将 Enqueue(x,Q)表示为 Insert(x,End(Q),Q)。实现Procedure
7、Enq ueue(x:Eleme ntType;var Q:QueueType);beginif Full(Q) then Error(The queue is full!)elsebeginQ.rear:=Q.rear mod MaxLe ngth+1;Q.EIeme ntsQ.rear:=x;en d;en d;Full是一个函数,若队列Q已满,则函数值为true,否则为false。Fun cti on Full(var Q:QueueType):Boolea n;beginRetur n( (Q.fro nt+MaxLe ngth-Q.rear=2)or(Q.fro nt-Q.rear=
8、2);en d;说明注意在计算队尾的位置时,如果用Q.rear:=(Q.rear+1) mod MaxLength,当 Q.rear=MaxLength-1 时就会出错,因此应该用 Q.rear:=Q.rear modMaxLe ngth+1。如图7(a)所示,队列满有两种情况,一种是Q.frontQ.rear且Q.front-Q.rear=2, 种是 Q.frontvQ.rear 且 Q.front+MaxLength-Q.rear=2,根据 这点可以实现Full函数。复杂性显然为0(1)。函数 Dequeue(Q)功能将Q的队头元素删除,简称为出队。用一般的表运算可将Dequeue(Q)表
9、示 为 Delete(First(Q),Q)。实现Procedure Dequeue(var Q:QueueType);beginif Empty(Q) the n Error(The queue is empty!)else Q.fr on t:=Q.fr ont mod MaxLe ngth +1;en d;说明显然。复杂性显然为0(1)。函数 Empty(Q)功能这是一个函数,若Q是一个空队列,则函数值为true,否则为false。实现Fun cti on Empty(var Q:QueueType):Boolea n;beginretur n(Q.fron t-Q.rear=1)or(
10、Q.fr on t+MaxLe ngth-Q.rear=1);en d;说明根据图6(a)知,队列空有两种情况,一种是Q.frontQ.rear且Q.front-Q.rear=1,一种是 Q.frontvQ.rear 且 Q.front+MaxLength-Q.rear=1。复杂性显然为0(1)。函数 MakeNull(Q)功能使队列Q成为空队列。实现Procedure MakeNull(Q);beginQ.fr on t:=2;Q.rear:=1;en d;说明用这种循环数组实现队列,不需要回收内存空间,因此MakeNull实现起来很简单,只要利用队列空的条件,使Q.fro nt-Q.rear=1即可。复杂性显然为0(1)。
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。