队列

队列

在日常生活中有许多“队列“的例子，如车站售票口买票的队伍，排在前面的人先买到票离开队伍，后来的人则加入队伍的末尾等候买票；其特点是“先进先出”(First In First Out)或“后进后出”(Last In Last Out)。

“队列”是在一端插入，另一端删除的特殊的线性表。进行删除的一端称为“队首”，进行插入的一端称为“队尾”(如下图)；插入也叫入队，删除则叫出队；在对队列进行操作时，一定要注意一头一尾。

队列可以用数组Q[1„ｍ]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：

f：队首指针，指向实际队头元素的前一个位置 r：队尾指针，指向实际队尾元素所在的位置 队列中拥有的元素个数为:L=r-f。一般情况下，两个指针的初值设为０，这时队列为空，没有元素。 1． 队列的定义 const

m=队列元素的上限； type

equeue= array [1..m] of qtype； {队列的类型定义} var

q:equeue； {队列}

f , r : integer； {队首指针与队尾指针} 3． 入队过程ADD(q,x,r)——在队列的尾端插入元素x

procedure ADD(var q: equeue ；x:qtype ；var r:integer)； begin

if r=m then writeln(‘overflow’) {队列满上溢}

else begin r:=r+1; q[r]:=x; end{else}

end;{add}

出队过程DEL(q,y,f,r)——取出q队列的队首元素y

procedure DEL(var q:equeue；var y:qtype；var f,r:integer)； begin

if f=r then writeln(‘underflow’) {队列空下溢} else begin f:=f+1；

y:=q[f]；

end；{else} end；{del}

例1、有N张牌，记为1，2，...，N，应当怎样排放，才能使：打开第一张是1，然后把两张依次放在末尾；打开上面一张，刚好是2，再依次打开上面一张，刚好是3；如此继续下去，直至打开最后一张是N。写一个程序解决这个问题。 解：Pascal程序： Program lt7_2_1;

var a,b:array[1..10000] of integer; i,j,t,h,n:integer; begin

readln(n);

for i:=1 to n do a[i]:=i; a[1]:=1;h:=2;t:=n;b[1]:=1; for i:=2 to n do begin

for j:=1 to i do begin

inc(t);a[t]:=a[h];inc(h); end;

b[a[h]]:=i;inc(h); end;

for i:=1 to n do write(b[i]:5); end. 分析：这是一个典型队列的例子，请大家仔细体会在队列操作过程中头指针和尾指针的变化。

例2、集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：

(1)数1属于M；

(2)如果X属于M，则Y=2*X+1和Z=3*X+1也属于M； (3)此外再没有别的数属于M。 解：Pascal程序： Program lt7_2_1;

var a,b:array[1..1000] of integer; x,ha,hb,t,total,n:integer; begin

assign(output,'data4.out');rewrite(output); readln(n); x:=1;a[1]:=1;

ha:=1;hb:=1;t:=0;total:=1;

while total<=n do begin

write(x,' '); inc(t);

a[t]:=2*x+1;b[t]:=3*x+1; if a[ha]>b[hb] then begin x:=b[hb];inc(hb); end

else begin x:=a[ha];

if a[ha]=b[hb] then inc(hb); inc(ha); end;

inc(total); end;

close(output); end.

分析：可以用两个队列来存放Y和Z中的数，分别用数组a和数组b存放。然后递推求出第N项，方法如下：

(1)令ha和hb分别为队列a和队列b的头指针，它们的尾指针为t。初始时，X=1，ha=hb=t=1； (2)将2*x+1和3*x+1分别放入队列a和队列b的队尾，尾指针加1。即： a[t]←2*x+1，b[t]←3*x+1，t←t+1；

(3)将队列a和队列b的头结点进行比较，可能有三种情况： (A)a[ha]>b[hb] (B)a[ha]=b[hb] (C)a[ha]将比较的小者取出送入X，取出数的队列的头指针相应加1。 (4)重复(2)，(3)直至取出第N项为止。

注意：数组的上标定到1000，当N较大时会出现队满溢出的情况，可以将上标定大些，或改用循环链表进行改进。

例3、求两个一元多项式的和。输入多项式方式为，多项式项数，每项系数和指数，按指数从大到小的顺序输入。 分析

多项式的算术运算是表处理的一个经典问题。建立两张表ａ、ｂ分别存放两个多项式的内容，建立表指针ta、tb，指向表ａ和表ｂ的元素，根据表ａ、ｂ元素中的指数大小合并输出。

１、比较ta、tb指向元素的大小，若ta的指数大于tb的指数，输出ta元素，改变指针ta；

2、若ta的指数小于tb的指数，输出tb元素，改变指针tb；

3、若ta的指数等于tb的指数，ta、tb元素的系数相加输出，同时改变指针ta和tb；

4、若有一表取空，则输出另一表剩余的内容。 源程序一：多项式相加的顺序表实现

program ex11_5a; type

node=record

zhi,xi:integer; end;

ar=array[1..1000] of node; var

a,b:ar;

ta,tb,n:integer; begin

write('One : '); readln(n);{输入第一个多项式的系数和指数} for ta:=n downto 1 do readln(a[ta].xi,a[ta].zhi); ta:=n;

write('Two : '); readln(n);{输入第二个多项式的系数和指数} for tb:=n downto 1 do readln(b[tb].xi,b[tb].zhi); tb:=n;

write('Result is ');

while (ta>0) and (tb>0) do {当两个表均不空时} begin

{比较两表指针指向的项指数,输出指数小的项系数和指数, 同时改变该表指针} if a[ta].zhi>b[tb].zhi then begin

if a[ta].xi<0 then write(#8' '#8); write(a[ta].xi,'x',a[ta].zhi,'+'); dec(ta); end else

if a[ta].zhiif b[tb].xi<0 then write(#8' '#8); write(b[tb].xi,'x',b[tb].zhi,'+'); dec(tb); end else

begin

{若两表指针指向的项指数相等,则两系数相加输出, 两表指针同时改变} if b[tb].xi+a[ta].xi<>0 then begin

if b[tb].xi+a[ta].xi<0 then write(#8' '#8);

write(b[tb].xi+a[ta].xi,'x',b[tb].zhi,'+'); end; dec(ta); dec(tb);

end; end;

while ta>0 do {若有一表空,则输出另一表的剩余项} begin

if a[ta].xi<0 then write(#8' '#8); write(a[ta].xi,'x',a[ta].zhi,'+'); dec(ta); end;

while tb>0 do begin

if b[tb].xi<0 then write(#8' '#8); write(b[tb].xi,'x',b[tb].zhi,'+'); dec(tb); end;

writeln(#8' '#8); readln; end.

练习二

1、高精度加法：

设计一个程序实现两个正整数(长度不超过200位)的求和运算。 解：Pascal程序： Program lx7_2_1； uses crt；

var a，b：string；

c，i，x，y，lm，ha，hb：integer； m：array[1..300] of integer； begin clrscr；

write('A=')；readln(a)； write('B=')；readln(b)；

ha：=length(a)；hb：=length(b)； c：=0；lm：=1；

while (ha>0) or (hb>0) do begin

if ha>0 then x：=ord(a[ha])-48 else x：=0；

if hb>0 then y：=ord(b[hb])-48 else y：=0； m[lm]：=x+y+c； c：=m[lm] div 10；

m[lm]：=m[lm] mod 10； inc(lm)；dec(ha)；dec(hb)； end；

if c>0 then m[lm]：=c else dec(lm)；

write(a，'+'，b，'=')； for i：=lm downto 1 do write(m[i])； end.

3、有1至2N的自然数，按从小到大的顺序排成一列，对这2N个数进行如下操作： （1）将这2N个数等分成A，B两组，即：

A组：1，2，...，N； B组：N+1，N+2，...，2N （2）轮流从A，B两组中按顺序取数： 1，N+1，2，N+1，...，N，2N

（3）再将取过的数等分为两组，并重复上述操作，直到这2N个数又按从小到大的顺序排好为止。

例如：当N=3时，操作如下： 初始序列为：1，2，3，4，5，6 (1) 1，4，2，5，3，6 (2) 1，5，4，3，2，6 (3) 1，3，5，2，4，6 (4) 1，2，3，4，5，6

分析：将1至2N的自然数分成两组，用两个队列来模拟上述过程即可。 4、有一个数，它的末位数字是N，将N移到这个数的首位，得到的新数恰好是原数的N倍，现输入N的值，求满足条件的最小的数。