数据结构（一）：栈的Java实现

栈实现的是一种后进先出（LIFO）策略。栈上的INSERT操作称为PUSH，而无元素参数的DELETE操作称为POP。可以使用一个数组来实现一个栈，该数组有一个属性，指向最新插入的元素。以下用Java实现了一个可变长度的堆栈，初始化时指定栈的初始长度，当堆栈空间不足时，数组自动复制并且容量扩容为以前的2倍。

import java.lang.reflect.Array;
import java.util.Arrays;

public class StackDemo<T> {
   private T[] array;
   private int top = -1;
   private int size = 0;
   private Class<T> T;

   @SuppressWarnings("unchecked")
   public StackDemo(Class<T> T, int size) {
	   this.size = size;
	   this.T = T;
	   this.array = (T[]) Array.newInstance(T, size);
   }

   public boolean push(T input) {
	   if (top >= size - 1) {
		   size *= 2;
		   array = Arrays.copyOf(array, size);
		   System.out.println(array.length);
	   }
	   top++;
	   array[top] = input;
	   return true;
   }

   public T pop() {
	   if (top < 0) {
		   return null;
	   } else {
		   top--;
		   return array[this.top + 1];
	   }
   }

   public boolean empty() {
	   if (top == -1)
		   return true;
	   else
		   return false;
   }

}