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繼續移動，以前的元素又被加進去…依次繼續下去