队列的实现

队列的链式和数组实现 循环队列的实现

/**
 * 文件名：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 = data;
			this.next = next;
		}
		
		private AnyType data;
		private Node<AnyType> next;
	}
	
	private Node<AnyType> front;
	private Node<AnyType> rear;
	public LinkedQueue(){
		clear();
	}
	public void clear(){
		front = null;
		rear = null;
	}
	public boolean isEmpty(){
		return front == null;
	}
	public void enqueue(AnyType x){
		if(front == null&&rear == null){//最开始的时候
			rear = new Node<AnyType>(x,null);
			front = rear;
		}else{
			Node<AnyType> p = new Node<AnyType>(x,null);
			rear.next = p;
			rear = p;;
		}
			
	}
	public AnyType dequeue(){
		if(!isEmpty()){
			AnyType x = front.data;
			front = front.next;
			return x;
		}
		return null;
	}
	public AnyType element(){
		if(!isEmpty())
			return front.data;
		return null;
	}
	
}
/**
 * 类名：QueueText
 * 说明：队列的数组和链表实现及循环队列的数组实现
 */
public class QueueText {
	/**
	 * 方法名：main
	 * 说明：测试
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/****数组队列测试*****/
		/*ArrayQueue<Integer> q = new ArrayQueue<Integer>();
		q.enqueue(1);
		q.enqueue(2);
		q.enqueue(3);
		q.enqueue(4);
		System.out.println(q.element());
		while(!q.isEmpty())
			System.out.println(q.dequeue());
	/*********链表队列测试**********/
		/*LinkedQueue<Integer> q2 = new LinkedQueue<Integer>();
		q2.enqueue(1);
		q2.enqueue(2);
		q2.enqueue(3);
		q2.enqueue(4);
		System.out.println(q2.element());
		while(!q2.isEmpty())
			System.out.println(q2.dequeue());
	/***********循环队列测试************/	
		CirArrQueue<Integer> q3 = new CirArrQueue<Integer>();
		q3.enqueue(1);
		q3.enqueue(2);
		q3.enqueue(3);
		q3.dequeue();
		q3.enqueue(4);//设置默认容量为3，开始时3个，队列满了，后来删除第一个，队列数组里第一个空出来了，4进入了，但是还是满足先进先出的原则，加上                               //size的控制，使其不会覆盖后面的
		q3.enqueue(5);//没有进去
		System.out.println(q3.element());
		while(!q3.isEmpty())
			System.out.println(q3.dequeue());
		
	}

}