linkedstack.java

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

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 class StackNode<T> 
 {
 	protected T data;
 	protected StackNode previous;
 	protected StackNode next;
 }
 
 public class LinkedStack<T>implements Stack<T>
 {
 	private StackNode head;
 	private StackNode tail;
 	private int len;
 	
 	public LinkedStack()
 	{
 		head = new StackNode();
 		tail = new StackNode();
 		head.next = tail;
 		tail.previous = head;
 		len = 0;
 	}
 	
 	public void insert(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				StackNode node = new StackNode();
 				node.data = elem;
 				cursor.previous.next = node;
 				node.previous = cursor.previous;
 				node.next = cursor;
 				cursor.previous = node;
 				len++;
 				return;
 			}
 			cursor = cursor.next;
 		}
 	}
 	
 	public T remove(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				T elem = (T)cursor.data;
 				cursor.previous.next = cursor.next;
 				cursor.next.previous = cursor.previous;
 				len--;
 				return elem;
 			}
 			cursor = cursor.next;
 		}
 		return null;
 	}
 	
 	public boolean remove(T elem)throws IndexSlopOverException
 	{
 		if(len==0)
 			throw new IndexSlopOverException();
 		StackNode cursor = head.next;
 		final int LENGTH = len;
 		while(cursor!=tail)
 		{
 			if(cursor.data.equals(elem))
 			{
 				cursor.previous.next = cursor.next;
 				cursor.next.previous = cursor.previous;
 				len--;
 			}
 			cursor = cursor.next;
 		}
 		if(len==LENGTH)
 			return false;
 		return true;
 	}
 	
 	public void push(T elem)
 	{
 		StackNode node = new StackNode();
 		node.data = elem;
 		tail.previous.next = node;
 		node.previous = tail.previous;
 		node.next = tail;
 		tail.previous = node;
 		len++;
 	}
 	
 	public T pop()throws IndexSlopOverException
 	{
 		StackNode top = tail.previous;
 		if(top==head)
 			throw new IndexSlopOverException();
 		T elem = (T)top.data;
 		top.previous.next = top.next;
 		top.next.previous = top.previous;
 		len--;
 		return elem;		
 	}
 	
 	public T peek()throws IndexSlopOverException
 	{
 		StackNode top = tail.previous;
 		if(top==head)
 			throw new IndexSlopOverException();
 		return (T)top.data;
 	}
 	
 	public void set(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
 			{
 				cursor.data = elem;
 				return;
 			}
 			cursor = cursor.next;
 		}
 	}
 	
 	public T get(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>=len)
 			throw new IndexSlopOverException();
 		int i = -1;
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(i==index)
				return (T)cursor.data;
 			cursor = cursor.next;
 		}
 		return null;
 	}	
 		
 	public boolean contains(T elem)
 	{
 		if(indexOf(elem)==-1)
 			return false;
 		return true;
 	}
 	
 	public int indexOf(T elem)
 	{
 		int i = -1;
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			if(cursor.data.equals(elem))
 				return i;
 			cursor = cursor.next;
 		}
 		return -1;
 	}
 	
 	public int size()
 	{
 		return len;
 	}
 	
 	public Object [] toArray()
 	{
 		if(len==0)
 			return null;
 		Object [] array = new Object[len];
 		int i = -1;
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			i++;
 			array[i] = cursor.data;
 			cursor = cursor.next;
 		}
 		return array;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(len==0)
 			return true;
 		return false;
 	}
 	
 	public void clear()
 	{
 		StackNode cursor = head.next;
 		while(cursor!=tail)
 		{
 			StackNode next = cursor.next;
 			cursor.previous = null;
 			cursor.next = null;
 			cursor = next;
 		}
 		head.next = tail;
 		tail.previous = head;
 		len = 0;
 	}
 	
 }