基本概念

栈：先进后出，后进先出。

栈是一种操作受限的线性表。仅允许在一端插入和删除数据。

数组/链表可以替代栈，但数组和链表暴露太多接口，操作上灵活自由，也就更容易出错。

如何实现栈

栈可以用数组，也可以用链表实现：

• 数组实现的栈，叫作顺序栈。
• 链表实现的栈，叫作链式栈。

这里使用数组来实现一个顺序栈：

// 基于数组实现的顺序栈
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;
  }
}