资源描述：
《队列的基本操作(xinn)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、队列的基本操作举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。出队进队A1A2A3A4……AN-1ANF（队头）R（队尾）一、队列的定义队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0。结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”
2、（FIFO—firstinfirstout）的线性表。队列的基本操作：（1）初始化队列Qini(Q)（2）入队QADD(Q,X)（3）出队QDel(Q,X)（4）判断队列是否为空qempty(Q)（5）判断队列是否为满qfull(Q)二、队列的存储结构1、顺序存储Constm=队列元素的上限；Typequeue=record{队列的类型定义}data:array[1..m]ofelemtypef,r:integer;{队尾指针和队首指针}end;Varq：queue；{队列}Constm=队列元素的上限；Typequeue=array[1..m]
3、ofelemtypeVarq：queue；{队列}f,r:integer;{队尾指针和队首指针}二、队列的存储结构2、链式存储FA1A2ANRtypelink=^celltype;celltype=recorddata:elemtype;next:link;end;varf,r:link;三、队列的基本运算1、初始化：设定Q为一空队列：procedureQini(varQ:queue);beginQ.f:=0;Q.r:=0;end;2、判队列空：若队列Q为空，则返回值true，否则返回值false。functionqempty(Q:queue):
4、Boolean;beginqempty:=(Q.f=q.r)end;functionqfull(Q:queue):Boolean;beginQfull:=（Q.r＝m);end;3、判队满：若队列满，则返回值true，否则返回值false。4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：procedureQADD(varq:queue;x:elemtype);beginifqfull(Q)thenwriteln(‘overflow’){上溢}elsebegin{后移队尾指针并插入元素x}Q.R:=Q.r
5、+1；Q.data[Q.r]:=x；end；{else}end；{ADD}5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：procedureQdel(varQ:queue;varX:elemtype);beginifqempty(Q)thenwriteln(‘Underflow’){下溢}elsebegin{后移队首指针并取出队首元素}Q.f←Q.f+1;X←Q.data[Q.f]；end；{else}end;例1假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的
6、队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数第二行舞曲的数目应用举例分析：设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=3n=2k=6A123123…………121212B…………F1R1F2R2constmax=10000;vara,b:array[1..max]ofinteger;m,n,k1,k,i,f1,r1,f2,r2:integer;beginreadln(m，n);f
7、ori:=1tomdoa[i]:=i;fori:=1tondob[i]:=i;readln(k);k1:=1;f1:=1;r1:=m;f2:=1;r2:=n;repeatwriteln(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;untilk1>kend.例2.集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：(1)数1属于M；(2)如果X属于M，则Y=2*X+1和Z=3*x+1也
8、属于M；(3)此外再没有别的数属于M。分析：可以用两个队列a和b来存放新产生的数，然后通过比较大小决定是否输出，具体方法如下：(1)令f
