队列的存储与实现

队列的存储与实现
队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。

链队列：

用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Gethead和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。

用指针实现队列时，单元类型及队列类型可说明如下:

type    queueptr=^queuenode;    queuenode=record               data:elemtp;               next:queueptr;              end;    linkedquetp=record                front,rear:queueptr;               end;

其中front为队头指针，rear为队尾指针。图2是用指针表示队列的示意图。file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image001.gif

图2

面我们来讨论队列的5种基本运算。

函数 Gethead(Q)

功能

这是一个函数，函数值返回队列Q的队头元素。

实现

FunctionGethead(var Q:linkedquetp):elemtp;

begin

ifEmpty(Q) then error('The queue is empty!')

            else return(Q.front^.next^.data);

end;

函数 Enqueue(Q,x)

功能

将元素x插入队列Q的队尾。此运算也常简称为将元素x入队。

实现

ProcedureEnqueue(x:elemtp;var Q:linkedquetp);

begin

new(Q.rear^.next);

Q.rear:=Q.rear^.next;

Q.rear^.data:=x;

Q.rear^.next:=nil;

end;

函数 Empty(Q)

功能

这是一个函数，若Q是一个空队列，则函数值为true，否则为false。

实现

FunctionEmpty(var QueueType):Boolean;

begin

return(Q.front=Q.rear);

end;

　

函数Dequeue(Q)

功能

将Q的队头元素删除，简称为出队。

实现

ProcedureDequeue(var Q:linkedquetp);

var

p:queueptr;

begin

ifEmpty(Q) then Error('The queue is empty!')

            else begin

                  p:=Q.front;

                  Q.front:=Q.front^.next;

                  dispose(p);

                 end;

end;

函数 Clear(Q)

功能

使队列Q成为空队列。

实现

Procedure clear(varQ:linkedquetp);

begin

Q.rear:=Q.front;

while Q.front<>nildo

   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;

循环队列：

我们可以将队列当作一般的表用数组实现，但这样做的效果并不好。尽管我们可以用一个游标last来指示队尾，使得Enqueue运算可在O(1)时间内完成，但是在执行Dequeue时，为了删除队头元素，必须将数组中其他所有元素都向前移动一个位置。这样，当队列中有n个元素时，执行Dequeue就需要O(n)时间。为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组中的单元不是排成一行，而是围成一个圆环，我们将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移一位，并在新的队尾游标指示的单元中存入新元素。出队操作也很简单，只要将队头游标Q.front依顺时针方向移一位即可。容易看出，用循环数组来实现队列可以在O(1)时间内完成Enqueue和Dequeue运算。执行一系列的入队与出队运算，将使整个队列在循环数组中按顺时针方向移动。通常，用队尾游标Q.rear指向队尾元素所在的单元，用队头游标Q.front指向队头元素所在单元的前一个单元，并且约定只能存放maxsize-1个元素如图3所示。

file:///C:/Users/20901/AppData/Local/Temp/msohtmlclip1/01/clip_image002.gif

　

图3

此时队列的定义如下：

constm=maxsize-1

typecyclicquetp=record

   elem:array[0..m] of elemtp;

   rear,front:0..m;

end;

varsq:cyclicquetp;

这时 当sq.rear=sq.front 时队空     当 (sq.rear+1) modmaxsize=sq.front 时队满

先sq.rear=( sq.rear+1) mod maxsize   后进队

先sq.front=（sq.front+1）modmaxsize 后出队

队列中元素的个数（sq.rear-sq.front+maxsize)mod maxsize