用循环数组实现队列 我们可以将队列当作一般的表用数组加以实现，但这样做的效果并不好。尽管我们可 以用一个游标 last 来指示队尾，使得 Enqueue 运算可在O(1) 时间内完成，但是在执行 Dequeue 时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样， 当队列中有 n 个元素时，执行 Dequeue 就需要O(n) 时间。 为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组 Q1.MaxLength中的单元不是排成一行，而是围成一个圆环，即 Q1 接在 QMaxLength 的后面。这种意义下的数组称为循环数组，如图 2 所示。 图 2 用循环数组实现队列 用循环数组实现队列时，我们将队列中从队头到队尾的元素按顺时针方向存放在循环 数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标 Q.rear 按顺时针方向移 一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标 Q.front 依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在O(1)时间内 完成 Enqueue 和 Dequeue 运算。执行一系列的入队与出队运算，将使整个队列在循环数 组中按顺时针方向移动。 在图 2 中，我们直接用队头游标 Q.front 指向队头元素所在的单元，用队尾游标 Q.rear 指向队尾元素所在的单元。另外，我们也可以用队头游标 Q.front 指向队头元素所 在单元的前一个单元，或者用队尾游标 Q.rear 指向队尾元素所在单元的下一个单元的方法 来表示队列在循环数组中的位置，如图 3 所示。 图 3 循环数组中的队头与队尾游标 在循环数组中，不论用哪一种方式来指示队头与队尾元素，我们都要解决一个细节问 题，即如何表示满队列和空队列。图 4 给出一个例子，MaxLength=6，队列中已有 3 个元 素。我们用上述 3 种方法来指示队头和队尾元素，分别如图 4(a)、(b)和(c)所示。 (a)(b) (c) 图 4 循环数组中的队列 现在，有 3 个元素 a 4 ,a 5 ,a 6 相继入队，使队列呈“满“ 的状态，则如图 5 相应的(a),(b)和 (c)所示。 (a)(b) (c) 图 5 队列满的情形 如果在图 4 中，3 个元素 a 1 ,a 2 ,a 3 相继出队，使队列呈“ 空“的状态，则如图 6 相应的(a), (b)和(c) 所示。 (a)(b) (c) 图 6 队列空的情形 比较图 5 和图 6 我们看到，不论采用哪一种方式指示队头和队尾元素，都需要附加说 明或约定才能区分满队列和空队列。 通常有两种处理方法来解决这个问题。其一是另设一个布尔量来注明队列是空还是满。 二是约定当循环数组中元素个数达到 MaxLength-1 时队列为“满”，使得队列满和队列空时 的队头和队尾游标的相对位置不同，从而满队列和空队列得以区分。例如，在图 4 中，当 元素 a 4 和 a 5 相继入队后，就便队列呈“ 满” 的状态，如图 7 所示。比较图 7 和图 6，显然只 要测试头和队尾游标的相对位置便可区分出满队列和空队列。(a) (b) (c) 图 7 改进后的队列满的情形 为确定起见，这里采用图 2 的方式定义 Q.front 和 Q.rear，另采用上述的第二种处理 法区分满队列和空队列。这样，队列的类型 QueueType 说明为： type TPosition=integer; QueueType = recordElements:array1.MaxLength of ElementType;front,rear:TPosition;end; 那么，在用循环数组实现的队列中，队列的 5 种基本运算可实现如下。其中表示空 元素，要根据不同的元素类型来确定。 函数 Front(Q) 功能 这是一个函数，函数值返回队列 Q 的队头元素。用一般的表运算 可将 Front(Q)表示为 Retrieve(First(Q),Q)。如果队列为空则返回空元素。 实现 Function Front(var Q:QueueType):ElementType; beginif Empty(Q) then return( )else return(Q.ElementsQ.front); end; 说明 显然 复杂性 显然为O(1) 。 函数 Enqueue(x,Q) 功能 将元素 x 插入队列 Q 的队尾。此运算也常简称为将元素 x 入队。也可用一般 的表运算将 Enqueue(x,Q)表示为 Insert(x,End(Q),Q) 。 实现 Procedure Enqueue(x:ElementType;var Q:QueueType); beginif Full(Q) then Error(The queue is full!)elsebegin Q.rear:=Q.rear mod MaxLength+1;Q.ElementsQ.rear:=x;end; end;Full 是一个函数，若队列 Q 已满，则函数值为 true，否则为 false 。Function Full(var Q:QueueType):Boolean; beginReturn(Q.front+MaxLength-Q.rear=2)or(Q.front-Q.rear=2); end;说明 注意在计算队尾的位置时，如果用 Q.rear:=(Q.rear+1) mod MaxLength ，当 Q.rear=MaxLength-1 时就会出错，因此应该用 Q.rear:=Q.rear mod MaxLength+1。 如图 7(a) 所示，队列满有两种情况，一种是 Q.frontQ.rear 且 Q.front- Q.rear=2，一种是 Q.frontQ.rear 且 Q.front- Q.rear=1，一种是 Q.frontQ.rear 且 Q.front+MaxLength-Q.rear=1。 复杂性 显然为O(1) 。 函数 MakeNull(Q) 功能 使队列 Q 成为空队列。 实现 Procedure MakeNull(Q); beginQ.front:=2;Q.rear:=1; end; 说明 用这种循环数组实现队列，不需要回收内存空间，因此 MakeNull 实现起来 很简单，只要利用队列空的条件，使 Q.front-Q.rear=1 即可。 复杂性 显然为O(1) 。