队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。
我们可以将队列当作一般的表用数组加以实现，但这样做的效果并不好。尽管我们可以用一个游标last来指示队尾，使得Enqueue运算可在O(1)时间内完成，但是在执行Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样，当队列中有n个元素时，执行Dequeue就需要O(n)时间。
为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组Q[1..MaxLength]中的单元不是排成一行，而是围成一个圆环，即Q[1]接在Q[MaxLength]的后面。这种意义下的数组称为循环数组，如图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个元素a4,a5,a6相继入队，使队列呈"满"的状态，则如图5相应的(a),(b)和(c)所示。
(a)
(b)
(c)
图5 队列满的情形
如果在图4中，3个元素a1,a2,a3相继出队，使队列呈"空"的状态，则如图6相应的(a),(b)和(c)所示。
(a)
(b)
(c)
图6 队列空的情形
比较图5和图6我们看到，不论采用哪一种方式指示队头和队尾元素，都需要附加说明或约定才能区分满队列和空队列。
通常有两种处理方法来解决这个问题。其一是另设一个布尔量来注明队列是空还是满。二是约定当循环数组中元素个数达到MaxLength-1时队列为“满”，使得队列满和队列空时的队头和队尾游标的相对位置不同，从而满队列和空队列得以区分。例如，在图4中，当元素a4和a5相继入队后，就便队列呈“满”的状态，如图7所示。比较图7和图6，显然只要测试头和队尾游标的相对位置便可区分出满队列和空队列。
(a)
(b)
(c)
图7 改进后的队列满的情形
为确定起见，这里采用图2的方式定义Q.front和Q.rear，另采用上述的第二种处理法区分满队列和空队列。
这样，队列的类型QueueType说明为：
|
type TPosition=integer; QueueType = record Elements:array[1..MaxLength] of ElementType; front,rear:TPosition; end; |
那么，在用循环数组实现的队列中，队列的5种基本运算可实现如下。其中∧表示空元素，要根据不同的元素类型来确定。
|
函数 Front(Q) 功能
实现
说明
复杂性
|
|
函数 Enqueue(x,Q) 功能
实现
说明
复杂性
|
|
函数 Dequeue(Q) 功能
实现
说明
复杂性
|
|
函数 Empty(Q) 功能
实现
说明
复杂性
|
|
函数 MakeNull(Q) 功能
实现
说明
复杂性
|
与栈的情形相同，任何一种实现表的方法都可以用于实现队列。用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Front和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。
用指针实现队列时，单元类型及队列类型可说明如下:
|
type TPosition=^NodeType; NodeType=record Element:ElementType; next:TPosition; end; QueueType=record front,rear:TPosition; end; |
其中front为队头指针，rear为队尾指针。图8是用指针表示队列的示意图。
图8 用指针实现队列
下面我们来讨论队列的5种基本运算。
函数 Front(Q)
功能
这是一个函数，函数值返回队列Q的队头元素。用一般的表运算可将Front(Q)表示为Retrieve(First(Q),Q)。
实现
Function Front(var Q:QueueType):ElementType;
begin
if Empty(Q) then error('The queue is empty!')
else return(Q.front^.next^.Element);
end;
说明
显然。
复杂性
显然为O(1)。
函数 Enqueue(x,Q)
功能
将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。也可用一般的表运算将Enqueue(x,Q)表示为Insert(x,End(Q),Q)。
实现
Procedure Enqueue(x:ElementType;var Q:QueueType);
begin
new(Q.rear^.next);
Q.rear:=Q.rear^.next;
Q.rear^.Element:=x;
Q.rear^.next:=nil;
end;
说明
图9是该操作修改指针的示意图。
图9 入队操作
复杂性
显然为O(1)。
函数 Dequeue(Q)
功能
将Q的队头元素删除，简称为出队。用一般的表运算可将Dequeue(Q)表示为Delete(First(Q),Q)。
实现
Procedure Dequeue(var Q:QueueType);
var
p:TPosition;
begin
if Empty(Q) then Error('The queue is empty!')
else begin
p:=Q.front;
Q.front:=Q.front^.next;
dispose(p);
end;
end;
说明
图10是该操作修改指针的示意图。
图10 出队操作
复杂性
显然为O(1)。
函数 Empty(Q)
功能
这是一个函数，若Q是一个空队列，则函数值为true，否则为false。
实现
Function Empty(var Q:QueueType):Boolean;
begin
return(Q.front=Q.rear);
end;
说明
当Q.front与Q.rear指向同一个结点单元时队列为空。
复杂性
显然为O(1)。
函数 MakeNull(Q)
功能
使队列Q成为空队列。
实现
Procedure MakeNull(var Q:QueueType);
begin
Q.rear:=Q.front;
while Q.front<>nil do
begin
Q.front:=Q.front^.next;
dispose(Q.rear);
Q.rear:=Q.front;
end;
new(Q.front);
Q.front^.next:=nil;
Q.rear:=Q.front;
end;
说明
首先将Q中所有的结点内存释放，然后重新生成一个结点作为标头单元，并使Q.rear:=Q.front。
复杂性
若输入的队列Q中有n个结点，则复杂性为O(n)。
/3 
文章评论（0条评论）
登录后参与讨论