聶永的博客

/**
 * 定義一個不可變棧
 * 
 * @author xiaomin
 * 
 * @param <T>
 */
public class DefaultStack<T extends Serializable> implements Stack<T> {

 private int size;

 private Object[] values;

 private int curr;

 public DefaultStack(int size) {
  this.size = size;

  curr = -1;

  values = new Object[size];
 }

 @Override
 public void push(T t) {
  if ((size - 1) == curr) {
   throw new UnsupportedOperationException("The Stack is full now !");
  }

  curr++;
  values[curr] = t;
 }

 @SuppressWarnings("unchecked")
 @Override
 public T pop() {
  if (curr < 0) {
   throw new UnsupportedOperationException("The Stack is empty now !");
  }

  return (T) values[curr--];
 }

 @Override
 public boolean end() {
  return curr == -1;
 }
}

/**
 * 定義一個鏈接結構的棧
 * 
 * @author xiaomin
 * 
 * @param <T>
 */
public class LinkStack<T extends Serializable> implements Stack<T> {

 /**
  * 定義一個節點
  * 
  * @author xiaomin
  * 
  */
 private class Node implements Serializable {
  private static final long serialVersionUID = 1L;

  private T value;
  private Node pre;

  // 構造一個空值
  public Node() {
   value = null;
   pre = null;
  }

  public Node(T value, Node pre) {
   this.value = value;
   this.pre = top;
  }
 }

 private Node top = new Node();

 @Override
 public void push(T t) {
  top = new Node(t, top);
 }

 @Override
 public T pop() {
  T value = top.value;

  if (!end())
   top = top.pre;

  return value;
 }

 @Override
 public boolean end() {
  return top.value == null && top.pre == null;
 }
}

/**
 * 定義一個不可變棧
 * 
 * @author xiaomin
 * 
 * @param <T>
 */
public class DefaultStack<T extends Serializable> implements Stack<T> {

 private int size;

 private Object[] values;

 private int curr;

 public DefaultStack(int size) {
  this.size = size;

  curr = -1;

  values = new Object[size];
 }

 @Override
 public void push(T t) {
  if ((size - 1) == curr) {
   throw new UnsupportedOperationException("The Stack is full now !");
  }

  curr++;
  values[curr] = t;
 }

 @SuppressWarnings("unchecked")
 @Override
 public T pop() {
  if (curr < 0) {
   throw new UnsupportedOperationException("The Stack is empty now !");
  }

  return (T) values[curr--];
 }

 @Override
 public boolean end() {
  return curr == -1;
 }
}

/**
 * 定義一個容量可變的棧
 * 
 * @author xiaomin
 * 
 * @param <T>
 */
public class ListStack<T extends Serializable> implements Stack<T> {

 private List<T> list = null;

 public ListStack() {
  list = new ArrayList<T>();
 }

 public ListStack(int size) {
  list = new ArrayList<T>(size);
 }

 @Override
 public void push(T t) {
  list.add(t);
 }

 @Override
 public T pop() {
  if (list.isEmpty()) {
   throw new EmptyStackException();
  }

  return list.remove(list.size() - 1);
 }

 @Override
 public boolean end() {
  return list.isEmpty();
 }
}

 public static void main(String[] args) {
  System.out.println("link stack ...\n");

  Stack<Integer> linkStack = new LinkStack<Integer>();
  int times = 10;

  testMethod(linkStack, times);

  System.out.println("\ndefault stack ...\n");
  Stack<Integer> defaultStack = new DefaultStack<Integer>(times);
  
  testMethod(defaultStack, times);
  
  System.out.println("\nlist stack with enouch space...\n");
  Stack<Integer> listStack = new ListStack<Integer>();

  testMethod(listStack, times*2);
 }

 private static void testMethod(Stack<Integer> linkStack, int times) {
  Random random = new Random(47);

  for (int i = 0; i < times; i++) {
   int value = i * random.nextInt(times);

   System.out.println("節點 " + (i + 1) + " : " + value);

   linkStack.push(value);
  }

  System.out.println("*********************************");

  int nums = times;
  while (!linkStack.end()) {
   System.out.println("節點 " + (nums--) + " : " + linkStack.pop());
  }
 }