java循环队列之舞会配对问题

题目

1. 利用循环队列模拟舞伴配对问题。在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。
2. 假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。
3. 从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。

正确代码

测试类

import java.util.Scanner;public class Test {public static void main(String[] args) {System.out.println("请输入跳舞轮数");Scanner sc=new Scanner(System.in);int round=sc.nextInt();SeqQueue boys=new SeqQueue(10); SeqQueue girls=new SeqQueue(10);boys.add("b1");boys.add("b2");boys.add("b3");boys.add("b4");boys.add("b5");girls.add("g1");girls.add("g2");girls.add("g3");int j=0;int min=minLength(boys,girls);while(j<round) {for(int i=0;i<min;i++) {String boy=boys.poll();String girl=girls.poll();System.out.println("boy"+boy+"<-->girls"+girl);		boys.add(boy);girls.add(girl);}/**注意* 必须要让int min=minLength(boys,girls);的min成为全局变量* 这样min就是固定的值，即两个队列中元素最少的那一队的元素个数，* 这样你每一次循环min就不变。* 如果把int min=minLength(boys,girls);这一行删除，* 并且for循环这里的min写成minLength(boys,girls)，* 那么每一次循环时，队列的front都会向后移动一位，* 每次调用minLength，我们发现int aLength=a.rear-a.front;的alength都会减少1，* minLength的值在这种情况下就不是固定的，* 因此要将min=minLength(boys,girls);写在for的外边。* **/System.out.println("没有被配对的第一个人是："+minSeqQueue(girls, boys).peek());j++;}}private static int minLength(SeqQueue a,SeqQueue b) {//这个比较大小的方法不可以比较队列数组的长度，数组的长度并不是元素的个数int aLength=a.rear-a.front;int bLength=b.rear-b.front;if(aLength<bLength) {return aLength;}else {return bLength;}}private static SeqQueue minSeqQueue(SeqQueue a,SeqQueue b) {if(a.element.length<b.element.length) {return a;}else {return b;}// TODO 自动生成的方法存根} }

队列类

public class SeqQueue {String element[];int front,rear;public SeqQueue(int length) {// TODO 自动生成的构造函数存根this.element=new String[length];this.front=this.rear=0;}public boolean isEmpty() {return this.front==this.rear;// TODO 自动生成的方法存根}public boolean add(String str) {if(this.front==(this.rear+1)%this.element.length) {String[] temp=this.element;this.element= new String[element.length*2];int j=0;for(int i=this.front;i!=this.rear;i=(i+1)%temp.length) {this.element[j++]=temp[i];}this.front=0;this.rear=j;}this.element[this.rear]=str;this.rear=(this.rear+1)%this.element.length;//System.out.println(this.element.length);return true;}public String peek() {// TODO 自动生成的方法存根return this.isEmpty()?null:this.element[front];}public String poll() {if (isEmpty()) {return null;}int temp=this.front;this.front=(this.front+1)%this.element.length;return this.element[temp];}
}

add方法的流程图（配合上面的代码看）

建议把代码copy到IDE中再看此流程图以获得最佳阅读效果，嘻嘻

循环队列原理及原理图

但是我们也可以发现，此时的循环队列宏观来看像是front向下移动，一旦循环完一个数组就开始访问第一个元素。可实质上由于front向下移动，访问过的元素又被加进了数组里，一旦加到数组满了，就再扩充数组的容量，然后front继续移动，以前的元素又被加进去…依次继续下去