arraystack.java

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

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 public class ArrayStack<T> implements Stack<T>
 {
 	private static final int INIT_SIZE = 1024;
 	private static final int INCREMENT = 256;
 	private Object [] stack;
 	private int size;
 	private int top;
 	
 	public ArrayStack()
 	{
 		stack = new Object[INIT_SIZE];
 		size = INIT_SIZE;
 		top = -1;
 	}
 	
 	private void extend()
 	{
 		Object [] tmpStack = new Object[size+INCREMENT];
 		for(int i=0;i<=top;i++)
 		{
 			tmpStack[i] = stack[i];
 		}
 		stack = tmpStack;
 	}
 	
 	public void insert(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>top)
 			throw new IndexSlopOverException();
 		if(top+1>=size)
 			extend();
 		for(int i=top;i>=index;i--)
 		{
 			stack[i+1] = stack[i];
 		}
 		stack[index] = elem;
 		top++;
 		
 	}
 	
 	public T remove(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>top)
 			throw new IndexSlopOverException();
 		T elem = (T)stack[index];
 		for(int i=index+1;i<=top;i++)
 		{
 			stack[i-1] = stack[i];
 		}
 		top--;
 		return elem;
 	}
 	
 	public boolean remove(T elem)throws IndexSlopOverException
 	{
 		if(top==-1)
 			throw new IndexSlopOverException();
 		int i = 0;
 		final int STACK_TOP = top;
 		while(i<=top)
 		{
 			if(stack[i].equals(elem))
 			{
 				for(int j=i+1;j<=top;j++)
 				{
 					stack[j-1] = stack[j];
 				}
 				top--; 				
 			}
 			else
 				i++;
 		}
 		if(top == STACK_TOP)
 			return false;
 		return true;
 	}
 	
 	public void push(T elem)
 	{
 		if(top+1>=size)
 			extend();
 		top++;
 		stack[top] = elem;
 	}
 	
 	public T pop()throws IndexSlopOverException
 	{
 		if(top==-1)
 			throw new IndexSlopOverException();
 		top--;
 		return (T)stack[top+1];
 	}
 	
 	public T peek()throws IndexSlopOverException
 	{
 		if(top==-1)
 			throw new IndexSlopOverException();
 		return (T)stack[top];
 	}
 	
 	public void set(int index,T elem)throws IndexSlopOverException
 	{
 		if(index<0 || index>top)
 			throw new IndexSlopOverException();
 		stack[index] = elem;
 	}
 	
 	public T get(int index)throws IndexSlopOverException
 	{
 		if(index<0 || index>top)
 			throw new IndexSlopOverException();
 		T elem = (T)stack[index];
 		return elem;
 	}
 	
 	public boolean contains(T elem)
 	{
 		if(indexOf(elem)==-1)
 			return false;
 		return true;
 	}
 	
 	public int indexOf(T elem)
 	{
 		for(int i=0;i<=top;i++)
 		{
 			if(stack[i].equals(elem))
 				return i;
 		}
 		return -1;
 	}
 	
 	public int size()
 	{
 		return top+1;
 	}
 	
 	public Object [] toArray()
 	{
 		if(top==-1)
 			return null;
 		Object [] array = new Object[top+1];
 		for(int i=0;i<=top;i++)
 		{
 			array[i] = stack[i];
 		}
 		return array;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(top==-1)
 			return true;
 		return false;
 	}
 	
 	public void clear()
 	{
 		stack = new Object[INIT_SIZE];
 		size = INIT_SIZE;
 		top = -1;
 	}
 }