栈（Stack）

栈是一种线性的数据结构。栈的操作比较特殊：只能在一端插入、删除和查看元素，其他部分则是不可见的。

• 栈是一种先进后出（FILO）的数据结构；

• 栈可以使用数组或链表来实现。使用数组实现的叫顺序栈，使用链表实现的叫链式栈；

• 入栈（push）和出栈（pop）是栈的两个重要操作；

• 栈的接口定义

  public interface Stack<E> {
      boolean isEmpty();      //返回是否是空栈
      int getSize();      //返回栈的大小
      void push(E e);     //入栈
      E pop();            //出栈
      E peek();           //获取栈顶元素
  }
  

• 使用数组实现

  public ArrayStack<E> implements Stack<E> {
      
      private Array<E> array;
      
      public ArrayStack(){
          array = new ArrayStack<>();
      }
      
      @Override
      public boolean isEmpty(){
          return array.isEmpty();
      }
      
      @Override
      public int getSize(){
          return array.getSize();
      }
      
      @Override
      public void push(E e){
          array.addLast(e);
      }
      
      @Override
      public E pop(){
          return array.removeLast();
      }
      
      @Override
      public E peek(){
          return getLast();
      }
  }
  

• 使用链表实现

  public LinkedList<E> implements Stack<E> {
      
      private LinkedList<E> list;
      
      public ArrayStack(){
          list = new LinkedList<>();
      }
      
      @Override
      public boolean isEmpty(){
          return list.isEmpty();
      }
      
      @Override
      public int getSize(){
          return list.getSize();
      }
      
      @Override
      public void push(E e){
          list.addLast(e);
      }
      
      @Override
      public E pop(){
          return list.removeLast();
      }
      
      @Override
      public E peek(){
          return getLast();
      }
  }