java数据结构之java实现栈

复制代码 代码如下:
import java.util.Arrays;

public class Stack {
 private int size;    //栈中元素的个数
 private Object[] arr;  //底层数组
 private final int defaultLength = 200; //默认长度

 
 public Stack(){
  arr = new Object[defaultLength];
  size = 0;
 }

 
 public Stack(int length){
  arr = new Object[length];
  size = 0;
 }

 
 public void push(T element){
  //是否需要扩容
  if(size >= arr.length){
   //数组扩容
   extendCapacity(size+1);
  }
  arr[size++] = element;
 }

 
 @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   arr[i]=null;
  }
  size = 0;
 }

 
 public int getSize(){
  return size;
 }

 
 public boolean isEmpty(){
  return size == 0;
 }

 
 @SuppressWarnings("unchecked")
 public void printStack(){
  for(int i=0;i   System.out.print(((T)arr[i]).toString());
  }
  System.out.println();
 }

 
 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);
  }
 }
}