arrayqueue.java

java 实现常用数据结构（链表

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 public class ArrayQueue<T> implements Queue<T>
 {
 	private static final int INIT_SIZE = 1024;
 	private static final int INCREMENT = 256;
 	private Object [] queue;
 	private int size;
 	private int len;
 	
 	public ArrayQueue()
 	{
 		queue = new Object[INIT_SIZE];
 		size = INIT_SIZE;
 		len = 0;
 	}
 	
 	private void extend()
 	{
 		Object [] tmpQueue = new Object[size+INCREMENT];
 		for(int i=0;i<len;i++)
 		{
 			tmpQueue[i] = queue[i];
 		}
 		queue = tmpQueue;
 	}
 	
 	public boolean add(T elem)
 	{
 		if(len>=size)
 			extend();
 		queue[len] = elem;
 		len++;
 		return true;
 	}
 	
 	public boolean remove(T elem)throws IndexSlopOverException
 	{
 		if(len==0)
 			throw new IndexSlopOverException();
 		int i = 0;
 		final int QUEUE_LENGTH = len;
 		while(i<len)
 		{
 			if(queue[i].equals(elem))
 			{
 				for(int j=i+1;j<len;j++)
 				{
 					queue[j-1] = queue[j];
 				}
 				len--; 				
 			}
 			else
 				i++;
 		}
 		if(len == QUEUE_LENGTH)
 			return false;
 		return true;
 	}
 	
 	public T poll()throws IndexSlopOverException
 	{
 		if(len==0)
 			throw new IndexSlopOverException();
 		T elem = (T)queue[0];
 		for(int i=1;i<len;i++)
 		{
 			queue[i-1] = queue[i];
 		}
 		len--;
 		return elem;
 	}
 	
 	public T peek()throws IndexSlopOverException
 	{
 		if(len==0)
 			throw new IndexSlopOverException();
 		return (T)queue[0];
 	}
 	
 	public boolean contains(T elem)
 	{
 		for(int i=0;i<len;i++)
 		{
 			if(queue[i].equals(elem))
 				return true;
 		}
 		return false;
 	}
 	
 	public int size()
 	{
 		return len;
 	}
 	
 	public Object [] toArray()
 	{
 		if(len==0)
 			return null;
 		Object [] array = new Object[len];
 		for(int i=0;i<len;i++)
 		{
 			array[i] = queue[i];
 		}
 		return array;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(len==0)
 			return true;
 		return false;
 	}
 	
 	public void clear()
 	{
 		queue = new Object[INIT_SIZE];
 		size = INIT_SIZE;
 		len = 0;
 	}
 }