队列及其应用

1、队列n队列的逻辑特征及抽象数据类型n队列的顺序表示和实现n队列的链式表示和实现队列的基本概念队列的基本概念队列基本操作：队列基本操作：（1）初始化 init()（2）是否为空 empty()（3）是否满 full() （4）入队 inqueue()（5）出队 delqueue()（6）取队头元素 gethead()（7）队列长度 lenqueue()队列的顺序存储方式（1）顺序存储：用数组表示，front和rear分别表示队头元素和队尾元素； 约定：front指向队头元素在队列中的前一个位置，rear指向队尾元素在队列中的当前位置。const qmaxsize=.;type qelement=

2、数据类型； queue=recorddata:array1.qmaxsizeof qelement;front,rear:0.qmaxsize; end;var q:queue;frontrear11顺序存储队列的基本操作(1)初始化 init() procedure init(var q:queue); beginq.front:=0;q.rear:=0; end;(2)是否为空 empty() function empty(var q:queue); beginempty:=(q.front=q.rear); end;(3)是否满 full() function full(var q:qu

3、eue); beginfull:=(q.rear=qmaxsize); end;顺序存储队列的基本操作(4)入队 inqueue(); procedure inqueue(var q:queue;x:qelement); beginif full(q) then writeln(FULL) else begin inc(q.rear);q.dataq.rear:=x; end;(5)出队 delqueue() procedure delqueue(var q:queue;x:qelement); beginif empty(q) then writeln(EMPTY)else begininc

4、(q.front);x:=q.dataq.front;end;(6)队头元素:m:=q.front+1;gethead:=q.datam(7)队列长度：lenqueue:=q.rear-q.front顺序队列的顺序队列的“ 假溢出假溢出” 问题问题顺序队列的“ 假溢出” 问题采用循环队列采用循环队列如何解决顺序队列的假溢出问题？顺序循环队列的表示顺序循环队列的表示顺序循环队列的表示队空和队满判断问题解决方案有三：使用一个计数器记录队列中元素个数（即队列长度）；判队满：(count0) and (rear=front)判队空：count=0加设标志位，出队时置,入队时置,则可识别当前front=

5、rear 属于何种情况判队满：(tag=1) and (rear=front)判队空：(tag=0) and (rear=front)少用一个存储单元判队满：front= (rear+1) mod MaxQueueSize判队空：rear=front方案三空队列和满队列顺序循环队列存储方式解决“假溢出”现象，q1接在qm之后，形成循环表，当删除a1之后插入am+1时，不移动队列中现有元素，直接把它加到q1位置上去。实际上就形成了一个环，这种队列称为循环队列循环队列。约定约定：损失一个元素空间。当front=rear时定义为空；当rear从后面追上front时，作为队满标志：rear+1=fro

6、nt032415032415032415032415front=rear=0空队列a1a2a3a4a5front=0rear=5a1.a5入队,队满front=3rear=5a1.a3出队a4a5a4a5a6a7a8rear=2front=3a6.a8入队，队满入队:rear:=(rear+1) mod max出队:front:=(front+1) mod max循环队列存储const maxsize=.;type qelement=数据类型; queue=recorddata=array0.maxsize-1of qelement;front，rear:0.maxsize-1; end;va

7、r q:queue;循环队列基本操作(1)初始化 init()procedure init(var q:queue);beginq.front:=0; q.rear:=0;end;(2)是否为空 empty()function empty(var q:queue):boolean;begin empty:=(q.front=q.rear);end;(3)是否溢出 full()function full(var q:queue):boolean;beginfull:=(q.(rear+1) mod maxsize=q.front);end;循环队列基本操作(4)入队 inqueue(var q:

8、queue; x:qelement);procedure inqueue(var q:queue;x:qelement);beginif full(q) then writeln(FULL)else begin q.rear:=(q.rear+1)mod maxsize; q.dataq.rear:=x;end;(5)出队 delqueue(var q:queue; x:qelement);procedure delqueue(var q:queue; x:qelement);beginif empty(q) then writeln(EMPTY)else begin q.front:=(q.

9、front+1）mod maxsize; x:=q.dataq.front;end;循环队列基本操作(6)队头元素 gethead(var q:queue):qelement; m:=(q.front+1)mod maxsize; gethead:=q.datam;(7)队列长度lenqueue(var q:queue):integer; lenqueue:=(q.rear-q.front+maxsize) mod maxsize;队列链接存储方式(2)链接存储：用一个单链表来实现。为了便于表示空队列，使用一个表头单元，将队头指针指向表头单元。type queueptr=queuenode;

10、queuenode=recorddata:elemtp; next:queueptr; end;linkedquetp=recordfront,rear:queueptr;end;q.frontq.rear.链接存储队列的基本操作(1)入队 inqueue(var q:linkedquetp;x:elemtp); procedure inqueue(var q:linkedquetp;x:elemtp); beginnew(q.rear.next);q.rear:=q.rear.next;q.rear.data:=x;q.rear.next:=nil; end;(2)出队 delqueue(v

11、ar q:linkedquetp;x:elemtp); procedure delqueue(var q:linkedquetp;x:elemtp); beginif empty(q) then writeln(EMPTY)else begin p:=q.front; q.front:=q.front.next; dispose(p);end链接存储队列的基本操作(3)置空队列 clear(q) procedure clear(var q:linkedquetp); beginq.rear:=q.front;while q.frontnil do begin q.front:=q.front.

12、next; dispose(q.rear); q.rear:=q.front; end;new(q.front);q.front.next:=nil;q.rear:=q.front; end;队列应用舞伴问题 假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。求

13、写一算法模拟上述舞伴配对问题。分析： 先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。具体参考程序代码program dancers;var dancer_name:array1.100 of string;

14、 /姓名 dancer_sex:array1.100 of char; /性别，F表示女性，M表示男性 F_dancer:array 1.100 of integer; F_front,F_rear:integer; /女士队列 M_dancer:array1.100 of integer; M_front,M_rear:integer; /男士队列 num,i,count:integer;begin F_front:=0; F_rear:=0; M_front:=0; M_rear:=0; write(请输入参加跳舞的人数：); readln(num); writeln(依次输入跳舞者的性别

15、、姓名：); for i:=1 to num do begin write(i,:); readln(dancer_sexi,dancer_namei); /输入性别，姓名 end; for i:=1 to num do /依次将跳舞者依其性别入队,只记录跳舞者数组的下标 begin if(dancer_sexi=F) then begin inc(F_rear); F_dancerF_rear:=i; /排入女队 end else begin inc(M_rear); M_dancerM_rear:=i; /排入男队 end; end; writeln(跳舞舞伴： ); while(F_fr

16、ontF_rear) and (M_frontM_rear) do begin /依次输出男女舞伴名 inc(F_front); /女士出队 write(dancer_nameF_dancerF_front, );/打印出队女士名 inc(M_front); /男士出队 writeln(dancer_nameM_dancerM_front); /打印出队男士名 end; if (F_frontF_rear) then begin /输出女士剩余人数及队头女士的名字 count:=F_rear-F_front; writeln(还有,count,位女士等待下一舞曲。); writeln( dan

17、cer_nameF_dancerF_front+1,将第一个获得舞伴); /取女队队头 end else begin if (M_front M_rear) then begin /输出男队剩余人数及队头者名字 count:=M_rear-M_front; writeln(还有,count, 位男士等待下一舞曲。); writeln(dancer_nameM_dancerM_front+1,将第一个获得舞伴。);/取男队队头 end; end; end.凯撒加密(Caesar cipher)【问题描述】凯撒加密(Caesar cipher)是一种简单的消息编码方式：它根据字母表将消息中的每个字

18、母移动常量位k。举个例子如果k等于3，则在编码后的消息中，每个字母都会向后移动3位：a会被替换为d；b会被替换成e；依此类推。字母表末尾将回卷到字母表开头。于是，w会被替换为z，x会被替换为a。在解码消息的时候，每个字母会反方向移动同样的位数。因此，如果k等于3，下面这条编码后的消息：vlpsolflwb iroorzv frpsohalwb会被解码成：simplicity follows complexity朱丽叶斯.凯撒在他的一些机密政府通信中真正用到了这种加密。遗憾的是，凯撒加密相当容易被破解。字母的移动只有26种可能；要破解密码，只需尝试各种密钥值，直到有一种可行即可。队列应用使用重复

19、密钥(repeating key)可以对这种编码技术做出改进，这时不再将每个字母移动常位数，而是利用一列密钥值将各个字母移动不同的位数。如果消息长于这列密钥值，可以从头再次使用这列密钥。例如，假设密钥值为：3 1 7 4 2 5则第1个字母会移动3位，第2个字母会移动1位，依此类推，将第6个字母移动5位之后，我们会从头再次使用这列密钥。于是第7个字母会移动3位，第8个字母会移动1位。反之解码的过程类似。注意：加密与解密都是针对字母（大小写均可）进行。样例：明文：this is a test! 密钥：2112 密文：viju kt b vgtu【算法分析】【算法分析】我们都知道队列的特点是我们都

20、知道队列的特点是FIFO(先进先出先进先出)，将密钥存储在队列中，将密钥存储在队列中，使用了一个密钥后，将这个密钥添加到队尾，这样较长的信息可以重复使用了一个密钥后，将这个密钥添加到队尾，这样较长的信息可以重复使用该密钥。使用该密钥。队列应用用队列实现图的宽度优先搜索算法 我们要对图进行分层次遍历,遍历的序列为1，2，7，宽度有先搜索算法遍历序列图宽度有先搜索算法遍历序列图分析 n 要对图进行按层次遍历，我们可采用逐层标号法要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：进行。方法如下：n 第一步：将初始点放入队列，并将该点设置为已第一步：将初始点放入队列，并将该点设置为已标号的点。标号的点。n 第二步：从队列中