Java_Datastructure.rar_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; } }