队列及其应用_fan

《队列及其应用_fan》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、队列及其应用安庆四中范江文队列队列是一种先进先出(FIFO)的线性表队列的顺序存储结构和链式存储结构队列必须构造成循环队列的形式,否则会出现“假溢出”队列基本操作：（1）初始化init()（2）是否为空empty()（3）是否满full()（4）入队inqueue()（5）出队delqueue()（6）取队头元素gethead()（7）队列长度lenqueue()一般队列存储方式（1）顺序存储：用数组表示，front和rear分别表示队头元素和队尾元素；约定：front指向队头元素在队列中的前一个位置，rear指向队尾元素在队列中的当前位置。constqmaxsi

2、ze=...;typeqelement=数据类型；queue=recorddata:array[1..qmaxsize]ofqelement;front,rear:0..qmaxsize;end;varq:queue;顺序存储a3a2a1a3a2a5a4rear=0front=0空队列front=0rear=3a1,a2,a3入队front=1rear=3a1出队front=3rear=3a2,a3出队front=3rear=5a4,a5入队顺序存储队列的基本操作(1)初始化init()procedureinit(varq:queue);beginq.front:

3、=0;q.rear:=0;end;(2)是否为空empty()functionempty(varq:queue);beginempty:=(q.front=q.rear);end;(3)是否满full()functionfull(varq:queue);beginfull:=(q.rear=qmaxsize);end;顺序存储队列的基本操作(4)入队inqueue();procedureinqueue(varq:queue;x:qelement);beginiffull(q)thenwriteln('FULL')elsebegininc(q.rear);q.dat

4、a[rear]:=x;end;(5)出队delqueue()proceduredelqueue(varq:queue;x:qelement);beginifempty(q)thenwriteln('EMPTY')elsebegininc(q.front);x:=q.data[q.front];end;(6)队头元素:m:=q.front+1;gethead:=q.data[m](7)队列长度：lenqueue:=q.rear-q.front一般队列存储方式(2)链接存储：用一个单链表来实现。为了便于表示空队列，使用一个表头单元，将队头指针指向表头单元。typequ

5、eueptr=^queuenode;queuenode=recorddata:elemtp;next:queueptr;end;linkedquetp=recordfront,rear:queueptr;end;a1a2anq.frontq.front....链接存储队列的基本操作(1)入队inqueue(varq:linkedquetp;x:elemtp);procedureinqueue(varq:linkedquetp;x:elemtp);beginnew(q.rear^.next);q.rear:=q.rear^.next;q.rear^.data:=x;

6、q.rear^.next:=nil;end;(2)出队delqueue(varq:linkedquetp;x:elemtp);proceduredelqueue(varq:linkedquetp;x:elemtp);beginifempty(q)thenwriteln('EMPTY')elsebeginp:=q.front;q.front:=q.front^.next;dispose(p);end链接存储队列的基本操作(3)置空队列clear(q)procedureclear(varq:linkedquetp);beginq.rear:=q.front;while

7、q.front<>nildobeginq.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[1]接在q[m]之后，形成循环表，当删除a1之后插入am+1时，不移动队列中现有元素，直接把它加到q[1]位置上去。实际上就形成了一个环，这种队列称为循环队列。约定：损失一个元素空间。当front=rear时定义为空；当rear从后面追上front时，作为队满标志：re

8、ar+1=