下载掌阅APP，畅读海量书库
立即打开
如果数组仿真队列进行插入一次删除一次的操作，只要2 n 次操作，数组就会用完，当数组仿真队列的元素出队后，队列的首部会空出许多位置，而队尾指针指向队列中最后一个元素位置，空出的位置将无法再被利用，导致队列空间浪费，并且在新的数据元素入队时，会造成“假溢出”，如图3.2所示。
图3.2
解决的方法是将线形数组模拟成环状数组。例如，一个有4个元素的环状数组a[4]的入队、出队操作如图3.3所示。
图3.3
可以看出：队满条件是rear＝front，队空条件也是rear＝front，所以无法判断究竟是队满还是队空。
解决方法是在入队时少用一个数据元素空间。
此时队满可用（rear＋1) %MaxSize＝front来判断，其中MaxSize为队列空间大小。
队空条件仍为rear＝front。
数组循环队列示例如下。
舞林大会吸引了很多人，参加比赛的女选手和男选手进入赛场时各自排成一队。比赛开始时，从男队和女队的队头上各出一人配成舞伴。规定每场比赛只能有一对跳舞者，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮，现要求输出第 k 轮的匹配情况。
第一行输入3个正整数，即男选手数 m 、女选手数 n 和 k 值（1≤ m ， n ≤1000，1≤ k ≤1000）。
输出第 k 轮的匹配情况。每一行为一个匹配。
2 4 6
2 2
设男选手组成一个队列，女选手组成一个队列，根据比赛规则，模拟队列的操作过程即可，参考程序如下。
Blah数集定义如下。
（1） a 是数集的基，且 a 是数集的第一个元素。
（2）如果 x 在数集中，则2 x ＋1和3 x ＋1也都在数集中。
（3）没有其他元素在数集中了。
请问：如果把数集中的元素按升序排列，第 n 个元素是多少？
输入包括很多行，每行输入包括两个元素，即数集的基 a （1≤ a ≤50）和所求元素序号 n （1≤ n ≤1000000）。
对于每一组输入，输出数集中的第 n 个元素。
1 100
28 5437
418
900585
除第一个元素 a 以外，数集中的所有元素都可被看作两个子集，即一个是用2 x ＋1来表示的集合 A ，一个是用3 x ＋1来表示的集合 B 。假设集合 A 中的某个元素是2 x ＋1，那么下一个元素为2(2 x ＋1)＋1，它们显然能组成一个升序数列，集合 B 同理。
设两个指针分别指向集合 A 和 B （程序中用队列表示）的最小值（队首元素），依次取两队的队首元素即可求出答案。
参考程序如下。
一个由“*”围成的图形，其面积的计算方法是统计“*”所围成的闭合曲线中水平线和垂直线交点的数目。在10×10的二维数组中，由“*”围住15个点，如图3.4所示，因此相应图形的面积为15。
图3.4
一个10×10的二维数组，里面的数为0和1，1代表“*”。
一个整数，即围住的区域数。
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
15
直接计算闭合区域的面积是很麻烦的，但是如果把这个闭合区域之外的数都转换成1的话，那么0的个数就是闭合区域的面积了。
参考程序如下，该程序使用队列实现了广度优先搜索（Breadth First Search，BFS）。
