循环队列的一个题目

1、    有500个小朋友拉成一个圆圈，从其中一个小朋友开始依次编号1－500，从1号小朋友开始循环1－3报数，数到3的小朋友就退出。编写一个Java应用程序，计算出最后一个小朋友的号码是多少？（20分）

这题可用一个简单的循环队列来模拟，但队列中剩余一个元素时就为我们的所要求的。

class DNode<T>{
	T value;
	DNode<T> next;
	DNode<T> pre;
	public DNode() {
		value = null;
		next = this;
		pre = this;
	}
	public DNode(T value){
		this.value = value;
	}
}
class DList<T>{
	DNode<T> header;
	DNode<T> curr;
	int size;
	public DList(){
		header = null;
		curr = header;
		size = 0;
	}
	public void add(T item){
		if(header == null){
			header = new DNode<T>(item);
			curr = header;
		}else{
			curr.next = new DNode<T>(item);
			curr.next.pre = curr;
			curr = curr.next;
			curr.next = header;
			header.pre = curr;
		}
		size++;
	}
	public void remover(DNode<T> node){
		node.pre.next = node.next;
		node.next.pre = node.pre;
		//System.out.println(node.value + "出队");
		node = null;
		size --;
	}
	public int size(){
		return size;
	}
	public T value(){
		return curr.value;
	}
	public DNode<T> next(){
		DNode<T> returnDNode = curr;
		curr = curr.next;
		return returnDNode;
	}
}
public class Game{
	DList<Integer> children;
	public Game(int n){
		children = new DList<Integer>();
		for(int i = 1; i <= n; i++){
			children.add(i);
		}
	}
	
	public int start(int step){
		int stepNums = 0;
		DNode<Integer> node = children.header;
		while(true){
			if(children.size() == 1){
				break;
			}
			
			if(++stepNums == step){
				children.remover(node);
				stepNums = 0;
			}
			node = node.next;
		}
		return node.value;
	}
	
	public static void main(String[] args) {
		Game game = new Game(10);
		System.out.println("最后留下：" + game.start(3));
	}
	
}