用指针实现队列_队列指针

函数 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)。

图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)。