用数组写出栈(先进后出)
<pre name="code" class="java">//用数组写出栈(先进后出)
import java.util.Collection; import java.util.NoSuchElementException; public class ArrayStack<E> { private int initalSize = 5; private Object[] stack; private int head; private int tail; public ArrayStack() { initialize(null); } public ArrayStack(int newcapacity){ if (newcapacity < this.initalSize) throw new IllegalArgumentException("The new capacity is too small!"); initalSize = newcapacity; initialize(null); } public ArrayStack(E[] items) { initialize(items); } public ArrayStack(Collection<E> collection) { initialize(collection.toArray()); } private void initialize(Object[] items){ if (items == null || items.length == 0){ stack = new Object[initalSize]; head = 0; tail = 0; } else{ stack = new Object[items.length + 1]; System.arraycopy(items, 0, stack, 0, items.length); head = items.length; tail = 0; } } @SuppressWarnings("unchecked") public E pop(){ if (size() == 0) throw new NoSuchElementException(); if (head == 0) head = stack.length; Object ret = stack[--head]; loseWeight(); return (E)ret; } public void push(E item){ increaseWeight(); stack[head++] = item; if (head == stack.length) head = 0; } @SuppressWarnings("unchecked") public E peek(){ if (size() == 0) throw new NoSuchElementException(); if (head == 0) return (E)stack[stack.length - 1]; else return (E)stack[head-1]; } public boolean isEmpty(){ return (size() == 0); } public int size(){ return head >= tail ? head - tail : head + stack.length - tail; } public boolean increaseWeight(){ if (size() == stack.length - 1){ Object[] newStack = new Object[stack.length * 2]; System.arraycopy(stack, 0, newStack, 0, stack.length); stack = newStack; return true; } return false; } public boolean loseWeight(){ if (size() == stack.length / 4){ Object[] newStack = new Object[stack.length/2]; if (head >= tail){ System.arraycopy(stack, tail, newStack, 0, size()); } else{ System.arraycopy(stack, tail, newStack, 0, stack.length-tail); System.arraycopy(stack, 0, newStack, stack.length-tail, head); } tail = 0; head = size(); return true; } return false; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。