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 }";
  }
}