资源描述：
《第13课 单行道问题——队列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第13课单行道问题——队列由于前面修路，交警叔叔把路改成了单行道，所有的车只能在入口排好一辆一辆地进入单行公路，在单行道中不能超车（因为公路的宽度只能够让一辆车通过），也不能后退（因为后面有车退不动），只有当它前面没有其他车的时候才能通过单行道出去，现在楠楠的车也在单行道中，她想知道自己是第几个开出单行道的人，你能用程序来帮她吗？例如：用不同的字符串代表不同的车，现在有C,Bfd,G,H,Ns,DD,E,S,EG按上面的顺序进入了单行道，楠楠的车是H，刚好是第4部开出单行道的车。【分析】（1）所有这些在单行道中的车可以看成是
2、由不同字符串所组成的一个数据表，我们用数组a来表示这个数据表，其中数据元素的下标，可以代表他们进入单行道时的顺序，如上例即是：a[1]='C',a[2]='Bfd',…,a[9]='EG'。（2）由于在单行道中的车是先进入就先出去，所以可以从数组的第一个元素开始扫描查找目标字符串，如果没有找到，就继续向下扫描。否则就输出元素下标，即是所求。Nannan(H)CBfdGHNsDDESEG读入“楠楠“字串读入数量到nFori:=1tondoreadln(a[i]);Na[i]:=nannan？输出i的值〖参考程序〗Program
3、p13_1;Vara:array[i..100]ofstring;i,n:integer;nannan:string;beginreadln(nannan);{读入代表楠楠的车的字串}readln(n);{读入共有n辆车进入了单行道}fori:=1tondoreadln(a[i]);{读入第i辆进入单行道中的车辆字符串}i:=0;repeat{从数组第一元素开始向后逐一查找代表楠楠车的字符串}i:=i+1;untila[i]=nannan;writeln(i);end.返回及进充电1、队列在实际生活中上，我们坐公交车要排队上
4、车，在超市买东西要排队付钱，这些就是我们常常见到的队列，它们的特点都是先到的排在前面，后到的排在后面。而在编程时，我们也用一种称为“队列”的数据组织方式来模仿日常生活中的队列。队列的操作特点是先进先出，后进后出，所有元素从一端进入，从另一端出去，就如汽车在单行道上行走时，只能在道路的一端进入，一端出去。我们把出去的一端称为“队首"(front),可以进入的一端称为“队尾”(rear)，如图13-1所示：出队列入队列a1a2a3……an队首队尾图13-1队列示意图2、循环队列如果用数组a[1..n]来存储队列时，数组的上界n即
5、是队列所容许的最大容量，如图13-2所示，当最后一个位置an已使用而还有数据要入队时，则会产生“溢出”，但前面的队首可能因元素出队而空出很多空间，这样就会白白浪费空间，而且队列又不能继续入队。出队列入队列…an队首队尾图13-2队列可以产生溢出的情形为了解决上面问题，把前面空出来的可用空间利用起来，我们对有n个存储单元的队列，只利用前n-1个单元，而最后一个位置an用作提示指针，指向绕到第1个位置，形成逻辑上的环状空间，这样当front或rear到达整个数组的末尾时，又可以回到开头，这样的队列我们称它是循环队列。如图13-3
6、所示：图13-3循环队列示意图我们约定，如图13-3所示，队尾(rear)指示到当前队尾元素所在位置的下一位，队首(front)指示队列中第一元素在数组中的位置。队首(front)和队尾(rear)均可以环绕数组移动，队列中腾出的空间就可以再利用，当front和rear的值大于了数组长度n时，我们就用求余运算使它们的值始终在[1..n]之间，就像时钟的指针经过了12点后总是又从1点开始一样(如17mod12=5).如图1-4所示，当队列的头尾重合，即front=rear时，这时队列为空;如图13-5所示，当front=(re
7、armodn)+1时，这时队列为满；其余时候，队列中的元素个数为：(rear-front+n)modn。图13-3队列为空图13-4队列为满探索奥秘〖例1〗芸芸和楠楠在玩扑克牌，她们共有n张扑克，这些扑克上分别记为1,2，…，n,芸芸打开扑克第一张是1，把它放在一边然后把最上面2张一张一张地依次移到最后，打开上面一张，刚好是3，放在一边。。。。。。如此继续下去，直至打开最后一张是n，放在一边，这时楠楠发现，放在一边的扑克刚好是按1,2，3……n这样排列的，好想知道，在开始的时候应当怎样排放这些扑克，才能得到这样的结果，你能帮
8、她写个程序求出扑克的最先排列顺序吗？例如：当n=5时，原排列是：14523;当n=9时，原排列是：186294537〖分析〗(1)把n张牌看成是1~n的n个数组成的队列，用数组a存放，用h指向队列a的队首。(2)用数组b来表示要求的原排列，因为b中的入队元素来自a中的出队元素，所以有b[i
