用循环数组实现队列

用循环数组实现队列我们可以将队列当作一般的表用数组加以实现，但这样做的效果并不好。尽管我们可 以用一个游标last来指示队尾，使得Enqueue运算可在0(1)时间内完成，但是在执行 Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样, 当队列中有n个元素时，执行Dequeue就需要0(n)时间。为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组 Q1.MaxLength中的单元不是排成一行，而是围成一个圆环，即Q1接在QMaxLength 的后面。这种意义下的数组称为循环数组，如图 2 所示。用循环数组实现队列时，我们将队列中从队头到队尾的元素按顺时针方向存放在循环 数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移 一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标 Q.fr ont依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在0(1)时间内完 成Enqueue和Dequeue运算。执行一系列的入队与出队运算，将使整个队列在循环数组 中按顺时针方向移动。在图2中，我们直接用队头游标Q.front指向队头元素所在的单元，用队尾游标Q.rear 指向队尾元素所在的单元。另外，我们也可以用队头游标Q.fro nt指向队头元素所在单元的 前一个单元，或者用队尾游标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相继出队，使队列呈"空"的状态，则如图6相应的(a),(b) 和(c)所示。(a)(b)Q. front Q- rear(c)图 6 队列空的情形比较图5和图6 我们看到，不论采用哪一种方式指示队头和队尾元素，都需要附加说 明或约定才能区分满队列和空队列。通常有两种处理方法来解决这个问题。其一是另设一个布尔量来注明队列是空还是满 二是约定当循环数组中元素个数达到M axLe ngth-1时队列为“满”，使得队列满和队列空时的 队头和队尾游标的相对位置不同，从而满队列和空队列得以区分。例如，在图4 中，当元 素a4和a5相继入队后，就便队列呈“满”的状态，如图7所示。比较图7和图6,显然只要 测试头和队尾游标的相对位置便可区分出满队列和空队列。(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)功能这是一个函数，函数值返回队列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 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=2);en d;说明注意在计算队尾的位置时，如果用Q.rear:=(Q.rear+1) mod MaxLength,当 Q.rear=MaxLength-1 时就会出错，因此应该用 Q.rear:=Q.rear modMaxLe ngth+1。如图7(a)所示，队列满有两种情况，一种是Q.front>Q.rear且Q.front-Q.rear=2, 种是 Q.frontvQ.rear 且 Q.front+MaxLength-Q.rear=2,根据 这点可以实现Full函数。复杂性显然为0(1)。函数 Dequeue(Q)功能将Q的队头元素删除，简称为出队。用一般的表运算可将Dequeue(Q)表示 为 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(Q.fr on t+MaxLe ngth-Q.rear=1);en d;说明根据图6(a)知，队列空有两种情况，一种是Q.front>Q.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)。