JAVA实现数组队列,循环数组队列,链式队列

/**
 * 文件名: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());
		
	}

}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。