/**
 * 文件名：QueueText.java
 * 时间：2014年10月22日下午9:05:13
 * 作者：修维康
 */
package chapter3;
/**
 * 类名：ArrayQueue
 * 说明：队列的数组实现
 */
class ArrayQueue<AnyType>{
	private static final int DEFAULT_CAPACITY = 10; 
	private int front;//队头
	private int rear;//队尾
	private int theSize;
	private AnyType[] theItems;
	public ArrayQueue(){
		clear();
	}
	public void clear(){
		front = 0;
		rear = 0;
		theSize = 0;
		ensureCapacity(DEFAULT_CAPACITY);
	}
	public boolean isEmpty(){
		return theSize == 0;//or front == rear;
	}
	public void  enqueue(AnyType x){
		theItems[rear++] = x;
		theSize++;
	}
	public AnyType dequeue(){
		if(theSize == 0)
			return null;
			theSize--;
		return theItems[front++];
	}
	//返回队列前面的元素
	public AnyType element(){
		if(isEmpty())
			return null;
		return theItems[front];
	}
	/**
	 * 方法名：ensureCapacity
	 * 说明：确保容量
	 */
	public void ensureCapacity(int newCapacity){
		if(newCapacity < theSize)
			return;
		AnyType[] old = theItems;
		theItems = (AnyType[]) new Object[newCapacity];
		for(int i = 0;i < theSize;i++)
			theItems[i] = old[i];
	}
	
}
/**
 * 类名：CirArrQueue
 * 说明：循环队列 (因为用数组实现的队列在删除的时候指针会后移 这样导致了前面的浪费，
 * 循环数组可以解决这个问题，但是循环队列可能使得运行时间加倍）
 */
class CirArrQueue<AnyType>{
	private static final int DEFAULT_CAPACITY = 3; 
	private int front;//队头
	private int rear;//队尾
	private int theSize;
	private AnyType[] theItems;
	public CirArrQueue(){
		clear();
	}
	public void clear(){
		theItems = (AnyType[]) new Object[DEFAULT_CAPACITY];
		front = 0;
		rear = 0;
		theSize = 0;
	}
	public boolean isEmpty(){
		return theSize == 0;//or front == rear;
	}
	public boolean  enqueue(AnyType x){
		if(theSize == DEFAULT_CAPACITY)
			return false;
		theItems[rear++] = x;
		theSize++;
		if(rear == DEFAULT_CAPACITY)//如果到了尾部则回到0
			rear = 0;
		return true;
	}
	public AnyType dequeue(){
		if(theSize == 0)
			return null;
			theSize--;
			AnyType temp = theItems[front];
			if(++front == DEFAULT_CAPACITY)//如果加1超过了数组 则返回到0;
				front = 0;
		return temp;
	}
	//返回队列前面的元素
	public AnyType element(){
		if(isEmpty())
			return null;
		return theItems[front];
	}
	
}
/**
 * 类名：LinkedQueue
 * 说明：链表实现队列
 */
class LinkedQueue<AnyType>{
	private static class Node<AnyType> {
		Node(AnyType data, Node<AnyType> next) {
			this.data = http://www.mamicode.com/data;>
JAVA实现数组队列，循环数组队列，链式队列