03-栈

栈

• 栈对应的操作，属于是数组的子集，因为添加元素和取出元素只能同一端，也就是栈顶
• 栈是一种后进先出的数据结构（LIFO），用户无法获取中间的元素
• 比如撤销操作、函数调用栈和代码编辑器的括号匹配等都用到了栈结构
• 由于栈的实现方式不仅是一种，所以写成接口的形式，方便多种实现

/**
 * @InterfaceName: Stack
 * @Description: 自定义栈接口
 */
public interface Stack<E> {
  /**
   * @MethodName: push
   * @Description: 将元素压入栈顶
   * @Param element: 入栈元素
   * @Return void
   */
  Void push (E element);

  /**
   * @MethodName: pop
   * @Description: 将栈顶元素从栈顶弹出
   * @Return E
   */
  E pop ();
  /**
   * @MethodName: peek 
   * @Description: 返回栈顶元素
   * @Return E
   */
  E peek ();
  
  /**
   * @MethodName: getSize 
   * @Description: 获取栈中的元素个数
   * @Return int
   */
  Int getSize ();

  /**
   * @MethodName: isEmpty 
   * @Description: 判断栈是否为空
   * @Return boolean
   */
  Boolean isEmpty ();
}

基于数组实现的栈

/**
 * @ClassName: ArrayStack
 * @Description: 基于自定义动态数组实现的自定义栈
 */
public class ArrayStack<E> implements Stack<E> {
  private Array<E> array;

  /**
   * @MethodName: ArrayStack
   * @Description: 根据用户需求创建指定大小容量的栈
   * @Param capacity: 用户指定的容量
   */
  Public ArrayStack (int capacity) {
    this. Array = new Array<>(capacity);
  }

  /**
   * @MethodName: ArrayStack
   * @Description: 为用户设置默认的容量大小，为 10
   */
  Public ArrayStack () {
    this. Array = new Array<>(10);
  }

  /**
   * @MethodName: push
   * @Description: 入栈操作实现
   * @Param element: 入栈元素
   * @Return void
   */
  @Override
  Public void push (E element) {
    This.Array.Add (this.GetSize (), element); //直接向数组最后添加元素即可
  }

  /**
   * @MethodName: pop
   * @Description: 出栈操作实现
   * @Return E
   */
  @Override
  Public E pop () {
    Return this.Array.Remove (this.GetSize () - 1); //直接将数组最后的元素删除并返回即可
  }

  /**
   * @MethodName: peek
   * @Description: 查看栈顶元素操作实现
   * @Return E
   */
  @Override
  Public E peek () {
    Return this.Array.Get (this.GetSize () - 1);  //返回数组最后一个元素
  }

  /**
   * @MethodName: getSize
   * @Description: 查看栈中元素个数操作实现
   * @Return int
   */
  @Override
  Public int getSize () {
    Return this.Array.GetSize (); //返回当前数组中元素的个数
  }

  /**
   * @MethodName: isEmpty
   * @Description: 查看栈是否为空操作实现
   * @Return boolean
   */
  @Override
  Public boolean isEmpty () {
    Return this.Array.IsEmpty ();  //返回当前数组是否为空
  }

  @Override
  Public String toString () {
    StringBuilder sb = new StringBuilder ();
    For (int i = 0; i < this.Array.GetSize (); i++) {
      Sb.Append (array.Get (i));
      If (i != this.Array.GetSize () - 1) {
        Sb.Append (",");
      }
    }
    Return "ArrayStack{" +
        "Stack=[" + sb.ToString () +
        "] top}";
  }
}

基于单向链表实现的栈

/**
 * @ClassName: LinkedListStack
 * @Description: 基于自定义单向链表实现的自定义栈
 */
public class LinkedListStack<E> implements Stack<E> {
  private LinkedList<E> list;

  /**
   * @MethodName: ArrayStack
   * @Description: 创建栈
   */
  Public LinkedListStack () {
    this. List = new LinkedList<>();
  }
  /**
   * @MethodName: push 
   * @Description: 入栈操作实现
   * @Param element: 入栈元素
   * @Return void
   */
  @Override
  Public void push (E element) {
    This.List.Add (0, element);  //直接向链表头部添加元素接即可
  }
  
  /**
   * @MethodName: pop 
   * @Description: 出栈操作实现
   * @Return E
   */
  @Override
  Public E pop () {
    Return this.List.Remove (0); //直接将链表头部元素删除并返回即可
  }

  /**
   * @MethodName: peek 
   * @Description: 查看栈顶元素操作实现
   * @Return E
   */
  @Override
  Public E peek () {
    Return this.List.Get (0);  //返回链表的第一个元素即可
  }
  
  /**
   * @MethodName: getSize 
   * @Description: 查看栈中元素个数操作实现
   * @Return int
   */
  @Override
  Public int getSize () {
    Return this.List.GetSize (); //返回当前链表中的元素个数
  }
  
  /**
   * @MethodName: isEmpty 
   * @Description: 查看栈是否为空操作实现
   * @Return boolean
   */
  @Override
  Public boolean isEmpty () {
    Return this.List.IsEmpty (); //返回当前链表是否为空
  }

  @Override
  Public String toString () {
    StringBuilder sb = new StringBuilder ();
    For (int i = this.List.GetSize () - 1; i >= 0; i--) {
      Sb.Append (list.Get (i));
      If (i != 0) {
        Sb.Append (",");
      }
    }
    Return "LinkedListStack{" +
        "Stack=[" + sb +
        "] top }";
  }
}