虽是读书笔记，但是如转载请注明出处http://segmentfault.com/blog/exploring/
..拒绝伸手复制党
想更一进步的支持我，请扫描下方的二维码，你懂的~

Stack

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
java 没有栈这样的数据结构，如果想利用先进后出（FILO）这样的数据结构，就必须自己实现。

要实现Stack，至少应该包括：
1. pop() 出栈操作，弹出栈顶元素。
2. push(E e) 入栈操作
3. PEek() 查看栈顶元素
4. iSEMpty() 栈为空

另外，实现一个栈，还应该考虑到几个问题：
1. 栈的初始大小以及栈满以后如何新增栈空间
2. 对栈进行更新时需要进行同步

有三种实现的方式，数组，容器，以及链表的方法。

数据：

package gsm; import java.util.*;  public class StackArray{     PRivate int[] array;//用数组实现     private int top; //栈顶指针     private final static int size = 100;     public StackArray(){         array = new int[size];         top = -1; //栈空的时候      }     //压栈     public void push(int element){         if(top == size-1){             throw new StackOverflowError();         }         else              array[++top] = element;     }     //弹栈     public int pop(){         if(top == -1){             throw new EmptyStackException();         }         return array[top--];     }     //判断是否为空     public boolean isEmpty(){         return top == -1;     }     //返回栈顶元素     public Integer peek(){         if(top == -1){             throw new EmptyStackException();         }         return array[top];     } } 

容器

package gsm;  public interface Stack<T> {     public T pop();     public void push(T element);     public boolean isEmpty();     public T peek(); }  package gsm; import java.util.*;  public class StackList<T> implements Stack<T> {     private List<T> list ; //用容器实现     StackList(){         list = new ArrayList<T>();     }     //弹栈     public T pop(){         if(this.isEmpty() == true){             throw new EmptyStackException();         }          return list.remove(list.size()-1);     }     //压栈     public void push(T element){         list.add(element);     }     //判断是否为空     public boolean isEmpty(){         return list.size() == 0;     }     //返回栈顶元素     public T peek(){         if(this.isEmpty() == true){             throw new EmptyStackException();         }         return list.get(list.size()-1);     } } 

链表

package gsm;  import java.util.EmptyStackException;  public class LinkedStack<T> implements Stack<T>{     //不用容器或者数组等数据结构存储节点     //Node定义一个节点类     private static class Node<U>{         private U item; //存储的data         private Node<U> next; //类似指针         Node(){             this.item = null;             this.next = null;         }         Node(U item, Node<U> next){             this.item = item;             this.next = next;         }         boolean end(){             return item == null &amp;& next == null;         }     }       private Node<T> top ; //栈顶指针     LinkedStack(){         top = new Node<T>();     }       //弹栈     public T pop(){         if(this.isEmpty() == true){             throw new EmptyStackException();         }         T result = top.item;         if(!top.end())         {             top = top.next;         }         return result;     }     //压栈     public void push(T element){         top = new Node<T>(element, top);     }     //判断是否为空     public boolean isEmpty(){         return  top.end();     }     //返回栈顶元素     public T peek(){         if(this.isEmpty() == true){             throw new EmptyStackException();         }         T result = top.item;         return result;     }    }