04| 栈

一、什么是栈？

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，后进者先出，先进者后出。
无论是数组或者是链表都可以实现栈的功能，栈只是一种特性的数据结构，可以理解为封装好的数组或者是封装好的链表。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

二、实现栈

栈的主要操作是入栈和出栈，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

一.顺序栈的实现（由数组封装）

这段代码是大佬自己写的，我参考一下，并写一个自己的顺序栈，链式栈的我自己写。

//大佬的代码
// 基于数组实现的顺序栈
public class ArrayStack {
   
     
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
   
     
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
   
     
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
   
     
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}