linkqueue.java

解迷宫的算法

package searchWay;
import java.util.EmptyStackException;

public class LinkQueue implements Queue {
		
	protected BidirectLinkNode head,headnode,tail;
	protected int size;
		//构造方法
	public LinkQueue() {
			
		//head指向头节点headnode，size默认为0
		//初始状态headnode的后继为head，head的后继为tail.
		headnode = new BidirectLinkNode();
		head = new BidirectLinkNode();
		tail = new BidirectLinkNode();
		head.prior = headnode;
		head.next = tail;
		headnode.prior = headnode;
		headnode.next = head;
		tail.prior=head;
		tail.next=tail;
		size=1;
	}
	
	//考察队是否为空，返回布尔型值.当头、尾节点的前驱一样时队为空
	public boolean empty() {
		return head==tail;
	}
	
	//察看队中第n个节点
	public BidirectLinkNode peek(int n){
	if (empty()&&n>size)
	throw new EmptyStackException();
	BidirectLinkNode s = headnode;
	for (int i = 0; i < n; i++)
		s = s.next;
	return s;
	}
	
	
	//从顶部添加一个元素
	public void push(BidirectLinkNode node) {
		BidirectLinkNode s = node;
		System.out.print("点<"+s.x+","+s.y+">入队"+"\n");
		s.index=size;
		s.prior=tail.prior;
		tail.prior.next=s;
		s.next=tail;
		tail.prior=s;
		size++;
	}
	
	//从取出尾部元素
	public BidirectLinkNode pop() {
		if (empty())
		throw new EmptyStackException();
		BidirectLinkNode e=tail.prior;
		tail.prior=tail.prior.prior;
		tail.prior.prior.next=tail;
		return e;
		}



}