else begin {后移队首指针并取出队首元素} Q.f←Q.f+1; X←Q.data[Q.f] ； end；{else}
end;
2007年冬令营
应用举例
第六讲 队列及应用
例1假设在周末舞会上，男士们和女士们
进入舞厅时，各自排成一队。跳舞开始
时，依次从男队和女队的队头上各出一
人配成舞伴。规定每个舞曲能有一对跳
2007年冬令营
第六讲 队列及应用
4、元素进队：若队列Q不满时，把元 素X插入到队列Q的队尾，否则返回信 息“Overflow”：
procedure QADD(var q:queue;x:elemtype); begin if qfull(Q) then writeln (‘overflow’) {上溢} else begin {后移队尾指针并插入元素x} Q.R:=Q.r+1； Q.data[Q.r]:=x； end；{else}
舞者。若两队初始人数不相同，则较长
的那一队中未配对者等待下一轮舞曲。
现要求写一个程序，模拟上述舞伴配对
问题。
输入：第一行两队的人数
第二行舞曲的数目
2007年冬令营
第六讲 队列及应用
分析：设计两个队列分别存放男士和女士。 每对跳舞的人一旦跳完后就回到队尾等待 下次被选。如m=3 n=2 k=6 F1 R1
(1)令fa和fb分别为队列a和队列b的头指 针，它们的尾指针为r。初始时，X=1， fa=fb=r=1；
end；{ADD}
2007年冬令营
第六讲 队列及应用
5、元素出队：若队列Q不空，则把队头 元素删除并返回值给X，否则输出信息 “Underflow”：
procedure Qdel(var Q:queue;var X:elemtype); begin if qempty(Q) then writeln(‘Underflow’) {下溢}
A 1 2 3 1 2 3 ………… F2 R2
B 1 2 1 2 1 2 …………
2007年冬令营
const max=10000;
第六讲 队列及应用
var a,b:array[1..max] of integer;
m,n,k1,k,i,f1,r1,f2,r2:integer;
begin
readln(m，n);
2007年冬令营
第六讲 队列及应用
• 结论：在队列这种数据结构中，最先 插入在元素将是最先被删除；反之最 后插入的元素将最后被删除，因此队 列又称为“先进先出”（FIFO—first in first out）的线性表。
2007年冬令营
第六讲 队列及应用
• 队列的基本操作： （1）初始化队列 Qini (Q) （2）入队 QADD(Q,X) （3）出队 QDel(Q,X) （4）判断队列是否为空 qempty(Q) （5）判断队列是否为满qfull(Q)
第六讲 队列及应用
队列的基本操作
•举例1：到医院看病，首先需ቤተ መጻሕፍቲ ባይዱ到挂 号处挂号，然后，按号码顺序救诊。
•举例2：乘坐公共汽车，应该在车站 排队，车来后，按顺序上车。
出队
A1 A2 A3 A4……AN-1 AN
进队
F（队头）
R（队尾）
2007年冬令营
一、队列的定义
第六讲 队列及应用
队列就是允许在一端进行插入，在另一 端进行删除的线性表。允许插入的一端 称为队尾，通常用一个队尾指针r指向 队尾元素，即r总是指向最后被插入的 元素；允许删除的一端称为队首，通常 也用一个队首指针f指向排头元素的前 面。初始时f=r=0。
end.
2007年冬令营
第六讲 队列及应用
例2.集合的前N个元素：编一个程序，按递增 次序生成集合M的最小的N个数，M的定义如 下：
(1)数1属于M； (2)如果X属于M，则Y=2*X+1和Z=3*x+1 也属于M； (3)此外再没有别的数属于M。
2007年冬令营
第六讲 队列及应用
分析：可以用两个队列a和b来存放新产生 的数，然后通过比较大小决定是否输出， 具体方法如下：
2007年冬令营
三、队列的基本运算
第六讲 队列及应用
1、初始化：设定Q为一空队列：
procedure Qini (var Q:queue); begin Q.f:=0; Q.r:=0; end;
2007年冬令营
第六讲 队列及应用
2、判队列空：若队列Q为空，则返回值 true，否则返回值false。
Var qf：, r:qiunetuege；er ;{队{队列尾} 指针和队首指针} f, r:enindt;eger ; {队尾指针和队首指针} Var q：queue； {队列}
2007年冬令营
二、队列的存储结构 2、链式存储
第六讲 队列及应用
F
A1
A2
AN
R
type link= ^celltype ; celltype=record data:elemtype; next:link; end; var f,r:link;
for i:=1 to m do a[i]:=i;
for i:=1 to n do b[i]:=i;
readln(k);
k1:=1;
f1:=1;r1:=m;f2:=1;r2:=n;
2007年冬令营
第六讲 队列及应用
repeat writeln(a[f1]:3,' ',b[f1]:3); r1:=r1+1;a[r1]:=a[f1]; f1:=f1+1 ; r2:=r2+1;b[r2]:=b[f2]; f2:=f2+1; k1:=k1+1; until k1>k
2007年冬令营
二、队列的存储结构
第六讲 队列及应用
1、顺序存储
CoCnsotnst m=m队=列队元列素元的素上的限上；限；
TypTeype quequuee=uaer=rraeyc[1o.r.dm{]队o列f 的ele类m型ty定pe义}
data : array[1..m] of elemtype
function qempty(Q:queue):Boolean; begin qempty:=(Q.f=q.r)
end;
2007年冬令营
第六讲 队列及应用
3、判队满：若队列满，则返回值true，否 则返回值false。 function qfull(Q:queue):Boolean; begin Qfull:=（Q.r＝m); end;