/**
 * 棧的實現<br>
 * @author Skip
 * @version 1.0
 */
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);
  }
 }
}