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;
		}



}