linkedqueue.java

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

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 class QueueNode<T>
 {
 	protected T data;
 	protected QueueNode previous;
 	protected QueueNode next;
 }
 
 public class LinkedQueue<T> implements Queue<T>
 {
 	private QueueNode head;
 	private QueueNode tail;
 	private int length;
 	
 	public LinkedQueue()
 	{
 		head = new QueueNode();
 		tail = new QueueNode();
 		head.next = tail;
 		tail.previous = head;
 		length = 0;
 	}
 	
 	public boolean add(T elem)
 	{
 		QueueNode node = new QueueNode();
 		node.data = elem;
 		tail.previous.next = node;
 		node.previous = tail.previous;
 		node.next = tail;
 		tail.previous = node;
 		length++;
 		return true;
 	}
 	
 	public boolean remove(T elem)throws IndexSlopOverException
 	{
 		if(length==0)
 			throw new IndexSlopOverException();
 		QueueNode cursor = head.next;
 		final int LENGTH = length;
 		while(cursor!=tail)
 		{
 			if(cursor.data.equals(elem))
 			{
 				cursor.previous.next = cursor.next;
 				cursor.next.previous = cursor.previous;
 				length--;
 			}
 			cursor = cursor.next;
 		}
 		if(length==LENGTH)
 			return false;
 		return true;
 	}
 	
 	public T poll()throws IndexSlopOverException
 	{
 		QueueNode first = head.next;
 		if(first==tail)
 			throw new IndexSlopOverException();
 		T elem = (T)first.data;
 		head.next = first.next;
 		first.next.previous = head;
 	    length--;
 	    return elem;
 	}
 	
 	public T peek()throws IndexSlopOverException
 	{
 		QueueNode first = head.next;
 		if(first==tail)
 			throw new IndexSlopOverException();
 		return (T)first.data;
 	}
 	
 	public boolean contains(T elem)
 	{
 		QueueNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			if(cursor.data.equals(elem))
 				return true;
 			cursor = cursor.next;
 		}
 		return false;
 	}
 	
 	public int size()
 	{
 		return length;
 	}
 	
 	public Object [] toArray()
 	{
 		if(length==0)
 			return null;
 		Object [] array = new Object[length];
 		int i = -1;
 		QueueNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			array[i] = cursor.data;
 			cursor = cursor.next;
 		}
 		return array;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(length==0)
 			return true;
 		return false;
 	}
 	
 	public void clear()
 	{
 		QueueNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			QueueNode next = cursor.next;
 			cursor.previous = null;
 			cursor.next = null;
 			cursor = next;
 		}
 		head.next = tail;
 		tail.previous = head;
 		length = 0;
 	}
 }