package stack;

 /**

  * 栈接口

  * @author jzj

  *

  * @param <E>

  */

 public interface Stack<E> {

     //入栈

     public void push(E e);

     //出栈

     public E pop();

     //取栈顶元素

     public E peek();

     //当前栈大小

     public int size();

     //栈是否为空

     public boolean isEmpty();

 }

 package stack;

 /**

  * 使用 单链表 实现栈

  * @author jzj

  *

  * @param <E>

  */

 public class LinkedStack<E> implements Stack<E> {

     private class Node {

         E data;//数据域

         Node next;//next域

         Node() {//栈底元素构造函数

             data = null;

             next = null;

         }

         /**

          * 非栈底元素构造函数

          * @param data 数据域

          * @param next 新建节点next域指向

          */

         Node(E data, Node next) {

             this.data = data;

             this.next = next;

         }

         //是否到栈底元素

         boolean isEnd() {

             return data == null && next == null;

         }

     }

     /*

      * 栈顶元素，刚开始时创建一个data与next域都为null的节点，它是一个标志性节点，

      * 也相当于栈底，如判断栈是否为空就可以使用它：如果top指向了这个节点，就表明已

      * 到栈底了，即栈为空

      */

     private Node top = new Node();

     //入栈

     public void push(E data) {

         //让栈顶指向新建节点

         top = new Node(data, top);

     }

     //出栈

     public E pop() {

         //该节点可能是栈底元素，如果是则返回为null

         E data = top.data;

         if (!top.isEnd()) {//如果不是栈底，则指向下一个元素

             top = top.next;

         }

         return data;

     }

     //取栈顶元素

     public E peek() {

         //该节点可能是栈底元素，如果是则返回为null

         return top.data;

     }

     //栈大小

     public int size() {

         int size = 0;

         Node tmpTop = top;

         while (tmpTop.next != null) {

             size++;

             tmpTop = tmpTop.next;

         }

         return size;

     }

     //栈是否为空

     public boolean isEmpty() {

         return top.isEnd();

     }

 }

 package stack;

 import java.util.LinkedList;

 /**

  * 使用 LinkedList 实现栈

  * @author jzj

  *

  * @param <E>

  */

 public class LinkedListStack<E> implements Stack<E> {

     private LinkedList<E> list = new LinkedList<E>();

     //入栈

     public void push(E e) {

         list.addFirst(e);

     }

     //出栈

     public E pop() {

         return list.removeFirst();

     }

     //取栈顶元素

     public E peek() {

         return list.getFirst();

     }

     //当前栈大小

     public int size() {

         return list.size();

     }

     //栈是否为空

     public boolean isEmpty() {

         return list.isEmpty();

     }

 }

 package stack;

 /**

  * 使用 数组 实现栈

  * @author jzj

  *

  * @param <E>

  */

 public class ArrayStack<E> implements Stack<E> {

     private E[] data;

     private int top = -1;//指向栈顶元素

     private int size = 3;

     public ArrayStack() {

         data = (E[]) new Object[size];

     }

     //入栈

     public void push(E e) {

         if ((top + 1) == size) {

             throw new IllegalStateException("stack full...");

         }

         data[++top] = e;

     }

     //出栈

     public E pop() {

         if (top == -1) {

             throw new IllegalStateException("stack empty...");

         }

         E tmp = data[top];

         //用完后释放对象，加快垃圾回收，防止大的对象不用发生内存泄露

         data[top] = null;

         top--;

         return tmp;

     }

     //取栈顶元素

     public E peek() {

         if (top == -1) {

             throw new IllegalStateException("stack empty...");

         }

         return data[top];

     }

     //当前栈大小

     public int size() {

         return top + 1;

     }

     //栈是否为空

     public boolean isEmpty() {

         return top == -1;

     }

 }

 package stack;

 import java.util.ArrayList;

 /**

  * 使用 ArrayList 实现栈

  * @author jzj

  *

  * @param <E>

  */

 public class ArrayListStack<E> implements Stack<E> {

     private ArrayList<E> list = new ArrayList<E>();

     //入栈

     public void push(E e) {

         list.add(e);//ArrayList默认就是在数组尾加入元素，从后面进

     }

     //出栈

     public E pop() {

         return list.remove(list.size() - 1);//从前面出

     }

     //取栈顶元素

     public E peek() {

         return list.get(list.size() - 1);

     }

     //当前栈大小

     public int size() {

         return list.size();

     }

     //栈是否为空

     public boolean isEmpty() {

         return list.isEmpty();

     }

 }