第二章第二章 队列队列 队列是限定在一端进行插入，另一端进行删除特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（FIFO）表。 队列可以用数组Qm+1来存储，数组的上界即是队列所容许的最大容量。在队列的运算中需设两个指针： head：队头指针，指向实际队头元素的前一个位置 tail：队尾指针，指向实际队尾元素所在的位置 一般情况下，两个指针的初值设为，这时队列为空，没有元素。图1 (a)画出了一个由个元素构成的队列，数组定义Q11。 Qi i=3,4,5,6,7,8 头指针head2，尾指针tail8。 队列中拥有的元素个数为:L=tail-head现要让队头的元素出队，则需将头指针加。即head=head+1这时头指针向上移动一个位置，指向Q3，表示Q3已出队。见图1 (b)。 如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q9入队，见图1 (c)。 当队尾已经处理在最上面时，即tail=10，见图1 (d)，如果还要执行入队操作，则要发生“上溢”，但实际上队列中还有三个空位置，所以这种溢出称为“假溢出”。 克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就翻转为。在结构上采用这种技巧来存储的队列称为循环队列，见图2 循环队的入队算法如下： 1、tail=tail+1； 2、若tail=n+1，则tail=1； 3、若head=tail尾指针与头指针重合了，表示元素已装满队列， 则作上溢出错处理； 4、否则，Qtail=x，结束（x为新入出元素）。 队列和栈一样，有着非常广泛的应用。 考虑一个分时系统，如果一台计算机联有四个终端，即允许四个用户同时使用这一台计算机。那么，计算机系统必须设立一个队列， 用以管理各终端用户使用CPU的请求。当某个用户要求使用CPU时，相应的终端代号就入队（插入队尾），而队头的终端用户则是CPU当前服务的对象。我们考虑最简单的情况， 对于当前用户（队头），系统每次分配一个为时间片的时间间隔，在一个时间片内，如果当前用户的作业没有结束，则该终端用户的代号出队后重新入队，插入队尾，等待下一次CPU服务。如果某个用户的作业运行结束，则先退出，出队后不再入队，整个运行过程就是各终端代号不断地入队、出队，CPU 轮流地为（）个终端用户服务。由于计算机的运行速度极快，所以，对于每个终端用户来说，似乎计算机是单独在为其服务。 和线性表一样，栈和队可以采用链表存储结构，当要实现多个栈共享内存或多个队共享内存时，选择链式分配结构则更为合适。【例例1】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数 第二行舞曲的数目【分析】：设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=4 n=3 k=6【参考程序参考程序】#include#includeusing namespace std;int a10001,b10001,k1=1,k,i,f1=1,r1,f2=1,r2;main() int m,n; cinmn; for (i=1;i=m;i+) ai=i; for (i=1;ik; r1=m; r2=n; while (k1=k) printf(%d %dn,af1,bf2); r1+; ar1=af1; f1+; /第一次am+1=a1=1,第二次am+2=a2=2,如此循环 r2+; br2=bf2; f2+; /第一次bn+1=b1=1,第二次bn+2=b2=2,如此循环 k1+; return 0; 【例例2】Blah数集数集【3.4数据结构之队列数据结构之队列2729】 大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下： (1)a是集合Ba的基，且a是Ba的第一个元素； (2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中； (3)没有其他元素在集合Ba中了。 现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？输入输入: 输入包括很多行，每行输入包括两个数字，集合的基a(1=a=50)以及所求元素序号n(1=n=1000000)输出输出: 对于每个输入，输出集合Ba的第n个元素值样例输入样例输入: 1 100 28 5437样例输出样例输出: 418 900585分析：分析： 题目要求输出集合中第n小的数，我们可以按照从小到大的顺序把序列中的前n个数计算出来，注意数集中除了第一个数a以外，其余每一个数y一定可以表示成2x+1或者3x+1的形式，其中x是数集中某一个数。因此除了第一数a以外，可以把数集q的所有数分成两个子集，一个是用2x+1来表示的数的集合1，另一个是用3x+1来表示的数的集合2，两个集合要保持有序非常容易，只需用两个指针two和three来记录，其中two表示集合1下一个要产生的数是由qtwo*2+1得到，three表示集合2下一个要产生的数是由qthree*3+1得到。接下来比较qtwo*2+1和qthree*3+1的大小关系： (1) qtwo*2+1=qthree*3+1：处理方法同上。 如此循环直到产生出数集的第n个数。【参考程序】【参考程序】#include#includeusing namespace std;const int N=1000100;long long qN;int a,n;void work(int a,int n)int rear=2;q1=a;int two=1,three=1;while(rear=n) long long t1=qtwo*2+1,t2=qthree*3+1; int t=min(t1,t2); if (t1t2) two+; else three+; if (t=qrear-1) continue; qrear+=t;coutqnan) work(a,n);return 0;【例例3】设有个人依次围成一圈，从第个人开始报数，数到第个人出列，然后从出列的下一个人开始报数，数到第个人又出列，如此反复到所有的人全部出列为止。设个人的编号分别为1，2，n，打印出列的顺序。【算法分析算法分析】 本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。人围成一圈，把一人看成一个结点，人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当人出列时，将结点的前继结点指针指向结点的后继结点指针，即把结点驱出循环链。1、建立循环链表。 当用数组实现本题链式结构时，数组ai作为指针变量来使用，ai存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j=aj，当数到m时，m结点出链，则aj=aaj。 当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；2、设立指针，指向当前结点，设立计数器，计数数到多少人；3、沿链移动指针，每移动一个结点，计数器值加，当计数器值为时， 则结点出链，计数器值置为。4、重复，直到n个结点均出链为止。【参考程序】用数组实现链式结构#includeusing namespace std;const int n=10,m=4; /设有10个人,报到4的人出列int an+1,j=n,k=1,p=0;main() for (int i=1;in;i+) ai=i+1; /建立链表 an=1; /第n人指向第1人，形成一个环 while (pn) /n个人均出队为止 while(km) /报数,计数器加1 j=aj; k+; printf(%d ,aj); p+; /数到m,此人出队,计数器置1 aj=aaj; k=1; return 0;【例例4】连通块描述描述: 一个n * m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。输入输入: 第一行两个整数n,m(1=n,m=100)，表示一个n * m的方格图。 接下来n行，每行m个整数，分别为0或1，表示这个格子是黑色还是白色。输出输出: 一行一个整数ans，表示图中有ans个黑色格子连通块。样例输入样例输入3 31 1 10 1 01 0 1样例输出样例输出3分析：分析： 我们可以枚举每个格子，若它是被涂黑的，且它不属于已经搜索过的联通块，则由它开始，扩展搜索它所在的联通块，并把联通块里的所有黑色格子标记为已搜索过。 如何扩展搜索一个联通块呢？我们用一个搜索队列，存储要搜索的格子。每次取出队首的格子，对其进行四连通扩展，若有黑格子，将其加入队尾,扩展完就把该格子删除。当队列为空时，一个联通块就搜索完了。 如样例所对应的方格图如下所示： 现在我们以样例为例模拟出这个方格图的搜索顺序： 将(1,1)加入队列，(1,1)表示左上角这个格子，当前队列为：(1,1)，联通块加1等于1。 取出队首的(1,1)，标记为已搜索并对其进行四连通扩展，扩展出(1,2)，删除(1,1)队列变为：(1,2)。 取出队首的(1,2)，标记为已搜索并对其进行四连通扩展，扩展到了(1,1)，(1,3)，(2,2)，(1,1)已经被标记搜索过，所以只将(1,3)，(2,2)加入队列，删除队首(1,2),队列变为：(1,3)，(2,2)。 取出队首的(1,3)，没有扩展出新格子，删除队首队列变为：(2,2) 取出队首的(2,2)，没有扩展出新格子，队列变为。完成以(1,1)开始的搜索。 将(3,1)加入队列，队列变为：(3,1)，联通块数加1变为2。 取出队首的(3,1)，没有扩展出新格子，删除队首队列变为。完成以(3,1)开始的搜索。 将(3,3)加入队列，队列变为：(3,3)，联通块数加1变为3。 取出队首的(3,3)，没有扩展出新格子，删除队首队列变为。完成以(3,3)开始的搜索。无法再加入新的元素，程序结束。【参考程序参考程序】#include using namespace std; const int N = 110; const int flag42 = 0, 1, 0, -1, 1, 0, -1, 0; int aNN,queueN * N2; int n, m, ans; bool pNN; void bfs(int x,int y) int front =0, rear =2; queue10 = x,queue11 = y; while (front rear-1) + front; x = queuefront0; y = queuefront1; for (int i = 0;i 4;+ i) int x1 = x + flagi0; int y1 = y + flagi1; if (x1 1 | y1 n | y1 m | !ax1y1 | px1y1) continue; px1y1 = true; queuerear0 = x1; queuerear+1 = y1; int mai