数据结构之栈

栈是一种很有意思的数据结构，它的特点是先入后出。大家可以想象一下弹夹，先被压入弹夹的子弹反而会后射出。

栈的特点

1. 先入后出
2. 只能从一端入栈或出栈

栈的构造

// 顺序栈
public class ArrayStack {
  private String[] items;  // 栈内元素
  private int current;       // 栈顶下标，-1代表空栈
  private int size;           //栈的大小

  // 构建一个容量为size的栈
  public ArrayStack(int size) {
    this.items = new String[size];
    this.size = size;
    this.current = -1;
  }

  // 入栈操作
  public boolean push(String item) {
    // 当栈顶下标等于容量-1时标识栈满，直接返回false，入栈失败。
    if (current == size-1) {
        return false;
    }
    // 移动栈顶指针
    current++
    // 将item放到栈顶
    items[current] = item;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (current == -1) {
       return null;
    }
    // 返回栈顶元素
    String tmp = items[current];
    current--;
    return tmp;
  }
  // 查看栈顶元素
  public String peek() {
    if (current == -1) {
       return null;
    }
    return items[current];
  }
}

可以看出不管是入栈还是出栈，空间复杂度和时间复杂度都是O(1)

栈的应用

栈适用于需要知道最近一次操作或者数据的场合。如leetCode第20题：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
解题思路：
遍历字符，遇到左扩号则压栈，遇到右扩号则弹出栈顶元素和有扩号进行匹配，若匹配成功则继续遍历，匹配失败则直接返回字符串非法

推荐练习

leetCode 20: 有效的扩号
leetCode 739: 每日温度
leetCode 227: 基本计算器2