队列的基本知识及应用

队列的基本知识及应用[内容提要]1．通过本章学习，掌握队列的定义及队列的存储结构2．掌握队列的基本操作运算：建队、插入、删除、队列空等，用数组、链接方式所建立队列及操作运算3．掌握循环队列概念及运算4．能够利用队列解决一些实际问题：广度优先搜索算法[重点难点]1．队列、循环队列概念及存储结构2．队列的基本操作3．综合运用队列结构解决实际问题[内容讲授]一、队列的基本知识队列(Queue)是一种特殊的线性表。它是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。1．队列的性质假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。图1队列的先进先出示意图2．队列的存储结构（1）顺序存储：可用记录数组实现（2）链接存储：用链接存储方式实现如图所示：frontrearA1A2A3………………An-1An顺序存储结构——数组3．基本术语：(1)队空：当队列中没有元素时称为空队列。(2)队满：当队列中单元全部被占用(3)队列操作规则：在队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。其出队操作规定从队头进行，进队操作从队尾进行。即队列的操作是依先进先出的原则进行的。(4)上溢、下溢：真溢、假溢4．队列的基本操作用顺序队列存储结构的表示方法：typequeue=recordvec:array[1..m]ofelemtypef,r:integer;end;f,r分别指向队列的头和尾（1）进队操作（插入运算）Procedureinsert(q,x);begin①ifq.r=mthen输出上溢②q.r:=q.r+1③q.vec[q.r]:=x;{进入队尾}④ifq.f=0thenq.f:=1end;（2）出队操作：删除操作proceduredele(q,x);begin链队示意图…a2rearfronta1∧①ifq.f=0then输出下溢②x=q.vec[q.f]③ifq.f=q.rthen[q.f=0;q.r=0]elseq.f:=q.f+1end;（3）置空队算法proceduresetnull(Q);beginq.f:=0;q.r:=0;end;5.循环队列为充分利用向量空间，克服假上溢现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（CircularQueue）。（1）定义：将队列的首、尾连接起来，形成一个环状。队尾指向m，队首指向1。对循环队列的操作：（2）插入操作：procedureinsert2(q.x);beginif(q.rmodm)+1=q.fthen溢出elseq.r:=[(q.rmodm)+1；q.vec[q.r]:=x]end;(3)删除操作:proceduredelete2(q,x);beginifq.f=q.rthen输出队空else[q.f=(q.fmodm)+1；x=q.vec[q.f]]end;(4)循环队列的长度：(r-f+n)modn6.链队列链队是指队列的链接存储表示，也就是说它只允许在表尾进行插入和在表头进行删除的单链表。一个链队需要队首、队尾两个指针，一个指向表头，一个指向表尾，如下图所示：设有如下的数据类型定义：typelinklist=^dynanode;dynanode=recorddata:elemtype;next:linklist;end;typelinkqueue=recordf,r:linklist;end;链接队列的操作运算如下：（1）插入算法procedureinsert(HQ,x);beginnew(p);p^.data:=x;p^.next:=nil;ifHQ.r=nilthen[HQ.f:=p;HQ.r:=p]else[HQ.r^.next:=p;HQ.r:=p]end;（2）删除算法proceduredelete(HQ,x);beginifHQ.f=nilthenerror(‘underflow‘);{队为空}x:=HQ.f^.data;p:=HQ.f;ifHQ.f=HQ.rthen[HQ.f:=nil;HQ.r:=nil]{删除结点}elseHQ.f:=HQ.f^.next;dispose(p);end;二、队列的应用队列在日常生活中应用很多，特别是在计算机科学领域中所起的作用很大。例如在解决主机与外部设备之间速度不匹配问题，解决多用户引起的资源竞争问题等，都运用了队列这样的数据结构算法，下面通过一些实例，了解运用队列解决问题方法。运用队列解决广度优先搜索算法中的最短路径问题是一种比较好的算法。例题1.1995年高中组基础题第4题，从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：1234567891011121314151617请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。（1）该题是一个路径搜索问题，根据图示，从入口（1）到出口（17）可以有多种途径，其中最短的路径只有一条，那么如何找最短路径是问题的关键。（2）根据题意，用一维数组存储各关卡号（设NO），用另一个数组存储访问到某关卡号的前趋关卡号（设PRE）。（3）由于本题是一个典型的图的遍历问题，此题可以采用图的广度优先遍历算法，并利用队列的方式存储顶点之间的联系。即访问一个点，将其后继结点入队，并存储它的前趋结点，直到最后从（17）点出口。（4）从最后出口的关卡号（17）开始回访它的前趋关卡号，则回返的搜索路径便是最短路径。（跳过许多不必要搜索的关卡）。（5）从列表中可以看出出口关卡号（17）的被访问路径最短的是：（17）←（16）←（19）←（18）←（1）←开始由此，我们得到广度优先遍历求最短路径的基本方法：访问一个点，将其后继结点入队，并存储它的前趋结点，直到所需要到达的地，然后通过最终目标点的结点的前驱记录，返回搜索最短路径的轨迹。例题2：如下图表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。12187312419851316614159170111222345681011111112城市交通图矩阵存储结构算法如下：用队列的方法。用a记录搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。具体过程如下：（1）将城市A入队，队首、队尾都为1。（2）将队首所指的城市所有可直通的城市入队（如果这个城市在队中出现过就不入队，可用一个集合来判断），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。程序如下：programexp_2;constju:array[1..8,1..8]of0..1=((1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1),(0,1,1,0,0,1,1,1),(0,1,0,1,1,1,0,1),(1,1,0,1,1,1,0,0),(0,0,1,1,1,1,1,0),(1,1,1,0,0,1,1,0),(1,1,1,1,0,0,0,1));typeR=record{记录定义}city:array[1..100]ofchar;pre:array[1..100]ofinteger;end;varh,d,i:integer;a:R;s:setof'A'..'H';procedureout;{输出过程}beginwrite(a.city[d]);repeatd:=a.pre[d];write('--',a.city[d]);untila.pre[d]=0;writeln;halt;end;proceduredoit;beginh:=0;d:=1;a.city[1]:='A';a.pre[1]:=0;s:=['A'];repeat{步骤2}inc(h);{队首加一，出队}fori:=1to8do{搜索直通的城市}if（ju[ord(a.city[h])-64,I]=0）and（not（chr（i+64）ins））then{判断城市是否走过}begininc(d);{队尾加一，入队}a.city[d]:=chr(64+i);a.pre[d]:=h;s:=s+[a.city[d]];ifa.city[d]='H'thenout;end;untilh=d;end;begin{主程序}doit;end.输出：H-F--A例题3迷宫问题：设有一个n*n方格的迷宫，入口和出口分别在左上角和右下角，如图所示，其走路规则是：在任何一个格子中，可以向8个方向前进，格子中0表示可以走，1表示不通，当迷宫给定后，找出一条从入口到出口的通路。入口出口迷宫图搜索的8个方向算法分析：（1）本题采用回溯算法，应用队列存放走过的路径：即先进先出，后进后出原理，输出走迷宫的路径。A[I,J]:=0表示可以走了1表示不可以走（2）超界条件为：x=1，xn,y1,yn,a[x,y]=1,入口处条件：x=1,y=1,x=n,y=1（3）增量和文字的方向：用数组表示程序如下：programexp_3;varA:array[1..20,1..20]of0…1;c:array[1..20,1..20]of0…1;b:array[o..400]ofinteger;dx,dy:array[1..20,1..20]of0…1;n,m,k,I,x,y:integer;beginwrite(‘n=‘);readln(n);fory:=1tondobegin{初始化程序段}forx:=1tondobeginread(a[x.y]);c[x,y]:=o;end;dx[1]：=1；dy[1]:=-1;dx[2]：=1；dy[2]:=0;dx[3]:=-1;dy[3]:=1;dx[4]:=-1;dy[4]:=0;0001101010110110010010010011010101000110011111010011101111000000dx[5]:=1;dy[5]:=1;dx[6]:=-1;dy[6]:=-1;dx[7]:=0;dy[7]:=1;dx[8]:=0;dy[8]:=-1;x:=1;y:=1;m:=0;k:=0;forI:=0to400dob[I]:=0;while(xn)or(y1)do{按八个方向搜索}begink:=k+1;ifk8thenbegin{八个方向均搜索后，无法前进}k:=b[m];m:=m-1;{退回到上一步}x:=x-dx[k];{清当前所走的记录内容}y:=y-dy[k];endelsebegin{可以向前走一步}x:=x+dx[k];y:=y+dy[k];if(x1)or(xn)or(y1)or(yn)or(a[x,y]=1)or(c[x,y]=1)thenbeginx:=x-dx[k];y:=y-dy[k];{超界或已经访问过，回退}endelsebeginm:=m+1;c[x,y]:=1;b[m]:=k;k:=0;{进队，记录所访问的格子}end;end;end;x:=1;y:=1;write(‘(‘,x,‘,‘,y,‘)‘);forI:=1tomdobeginx:=x+dx[b[I]];y:=y+dy[b[I]];write(‘-(‘,x,‘,‘,y,‘)‘);end;writeln;end.程序运行结果：(1,1)——（2，1）——（3，1）——（2，2）——（1，3）——