- import java.util.Arrays;
- /**
- * 栈的实现<br>
- */
- public class Stack<T> {
- private int size; //栈中元素的个数
- private Object[] arr; //底层数组
- private final int defaultLength = 200; //默认长度
- /**
- * 无参构造,使用默认长度初始化数组
- */
- public Stack(){
- arr = new Object[defaultLength];
- size = 0;
- }
- /**
- * 使用长度参数初始化数组
- * @param length 长度
- */
- public Stack(int length){
- arr = new Object[length];
- size = 0;
- }
- /**
- * 入栈
- * @param element 数据
- */
- public void push(T element){
- //是否需要扩容
- if(size >= arr.length){
- //数组扩容
- extendCapacity(size+1);
- }
- arr[size++] = element;
- }
- /**
- * 出栈
- * @return 数据
- */
- @SuppressWarnings("unchecked")
- public T pop(){
- //元素个数为0,无法执行出栈操作
- if(size==0){
- return null;
- }
- T t = (T)arr[size-1];
- arr[--size] = null; //数据已出栈,还原为null
- return t;
- }
- /**
- * 清空栈
- */
- public void clear(){
- for(int i=0;i<size;i++){
- arr[i]=null;
- }
- size = 0;
- }
- /**
- * 获得当前栈中元素的个数
- * @return 元素的个数
- */
- public int getSize(){
- return size;
- }
- /**
- * 判断是否为空栈
- * @return 空为true,非空为false
- */
- public boolean isEmpty(){
- return size == 0;
- }
- /**
- * 打印栈中所有的元素
- */
- @SuppressWarnings("unchecked")
- public void printStack(){
- for(int i=0;i<size;i++){
- System.out.print(((T)arr[i]).toString());
- }
- System.out.println();
- }
- /**
- * 扩容
- * @param length 需要的长度
- */
- private void extendCapacity(int length){
- //当前数组长度和需要的长度取最大
- int minCapacity = Math.max(arr.length, length);
- //判断是否需要扩容
- if(minCapacity - arr.length>0){
- //数组长度增加一半
- int newLength = arr.length + arr.length/2;
- //如果新的长度还比需求要小,将需求的长度作为数组长度
- if(newLength < minCapacity){
- newLength=minCapacity;
- }
- //数组长度不能超过Integer.Max_Value
- if(newLength > Integer.MAX_VALUE - 8){
- newLength = Integer.MAX_VALUE;
- }
- //数组扩容
- arr = Arrays.copyOf(arr, newLength);
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1405201512581.html
来源: http://www.codesnippet.cn/detail/1405201512581.html