队列用例：Josephus问题

/**
 * 据说著名犹太历史学家 Josephus有过以下的故事：
 * 在罗马人占领乔塔帕特後，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，
 * 于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，
 * 直到所有人都自杀身亡为止。
 * 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，
 * 于是逃过了这场死亡游戏。
 *
 */
public class JosephusProblem {

	static int N = 41;
	
	public static void main(String[] args) {
		int M = 3;//数到第N个时自杀
		Queue<Integer>q1 = new LinkQueue<Integer>();
		for(int i = 0;i<N;i++){
			q1.push(i+1);
		}
		kill(q1,M,0,1);
	}
	
	/**
	 * @param q 队列
	 * @param n 数到第N个时自杀
	 * @param i 本论自杀数数完毕之后数到了第几
	 * @param level 第几轮
	 */
	public static void kill(Queue<Integer> q,int n,int i,int level){
		formatPrintln(q);
		if(q.isEmpty() || q.size()==1){
			if(q.size()==1){
				System.out.println("survivor:"+q.pop());
			}
			return;
		}
		Queue<Integer> survivors = new LinkQueue<Integer>();
		int peopleIndex = 0;
		while(!q.isEmpty()){
			peopleIndex = q.pop();
			i++;//报数
			if(i==n){
				formatPrint("^");
				i = 0;
			}else{
				survivors.push(peopleIndex);
				formatPrint();
			}
		}
		System.out.println();
		for(int x = 0;x<N;x++){
			System.out.print("-----");
		}
		System.out.println();
		kill(survivors,n,i,++level);
	}
	
	private static void formatPrintln(Queue<Integer> q){
		for(Integer i : q){
			System.out.print(fullBlank(i+""));
		}
		System.out.println();
	}
	private static void formatPrint(String str){
			System.out.print(fullBlank(str));
	}
	private static void formatPrint(){
		System.out.print(fullBlank(""));
	}
	private static String fullBlank(String str){
		if(str.length()<5){
			str = str+ ("     ".substring(0,5-str.length()));
		}
		return str;
	}
}

运行结果：

1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   
          ^              ^              ^              ^              ^              ^              ^              ^              ^              ^              ^              ^              ^              
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1    2    4    5    7    8    10   11   13   14   16   17   19   20   22   23   25   26   28   29   31   32   34   35   37   38   40   41   
^              ^              ^              ^              ^              ^              ^              ^              ^              ^    
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2    4    7    8    11   13   16   17   20   22   25   26   29   31   34   35   38   40   
          ^              ^              ^              ^              ^              ^    
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2    4    8    11   16   17   22   25   29   31   35   38   
          ^              ^              ^              ^    
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2    4    11   16   22   25   31   35   
          ^              ^              
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2    4    16   22   31   35   
^              ^              
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4    16   31   35   
^              ^    
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
16   31   
          
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
16   31   
^         
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
31   
survivor:31