/**
 * 棧的實(shí)現(xiàn)<br>
 * @author Skip
 * @version 1.0
 */
public class Stack<T> {
 private int size;    //棧中元素的個(gè)數(shù)
 private Object[] arr;  //底層數(shù)組
 private final int defaultLength = 200; //默認(rèn)長(zhǎng)度

 /**
  * 無參構(gòu)造,使用默認(rèn)長(zhǎng)度初始化數(shù)組
  */
 public Stack(){
  arr = new Object[defaultLength];
  size = 0;
 }

 /**
  * 使用長(zhǎng)度參數(shù)初始化數(shù)組
  * @param length 長(zhǎng)度
  */
 public Stack(int length){
  arr = new Object[length];
  size = 0;
 }

 /**
  * 入棧
  * @param element 數(shù)據(jù)
  */
 public void push(T element){
  //是否需要擴(kuò)容
  if(size >= arr.length){
   //數(shù)組擴(kuò)容
   extendCapacity(size+1);
  }
  arr[size++] = element;
 }

 /**
  * 出棧
  * @return 數(shù)據(jù)
  */
 @SuppressWarnings("unchecked")
 public T pop(){
  //元素個(gè)數(shù)為0,無法執(zhí)行出棧操作
  if(size==0){
   return null;
  }
  T t = (T)arr[size-1];
  arr[--size] = null;  //數(shù)據(jù)已出棧,還原為null
  return t;
 }

 /**
  * 清空棧
  */
 public void clear(){
  for(int i=0;i<size;i++){
   arr[i]=null;
  }
  size = 0;
 }

 /**
  * 獲得當(dāng)前棧中元素的個(gè)數(shù)
  * @return 元素的個(gè)數(shù)
  */
 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();
 }

 /**
  * 擴(kuò)容
  * @param length 需要的長(zhǎng)度
  */
 private void extendCapacity(int length){
  //當(dāng)前數(shù)組長(zhǎng)度和需要的長(zhǎng)度取最大
  int minCapacity = Math.max(arr.length, length);
  //判斷是否需要擴(kuò)容
  if(minCapacity - arr.length>0){
   //數(shù)組長(zhǎng)度增加一半
   int newLength = arr.length + arr.length/2;
   //如果新的長(zhǎng)度還比需求要小,將需求的長(zhǎng)度作為數(shù)組長(zhǎng)度
   if(newLength < minCapacity){
    newLength=minCapacity;
   }
   //數(shù)組長(zhǎng)度不能超過Integer.Max_Value
   if(newLength > Integer.MAX_VALUE - 8){
    newLength = Integer.MAX_VALUE;
   }
   //數(shù)組擴(kuò)容
   arr = Arrays.copyOf(arr, newLength);
  }
 }
}