3. 栈

栈是一种遵从先进后出 (LIFO) 原则的有序集合

栈的特点是只能在某一端（只有一个口子）添加或删除数据，遵循先进后出的原则

插入操作在栈中被称作入栈（push）

删除操作栈中被称作退栈（pop）

使用场景：方法调用，作用域

class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    return this.stack.push(item);
  }
  pop() {
    return this.stack.pop();
  }
  peek() {
    return this.stack[this.getSize() - 1];
  }
  getSize() {
    return this.stack.length;
  }
  isEmpty() {
    return this.getSize() === 0;
  }
}

栈的应用：

有效的括号 (opens new window)

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

解题思路：

分析测试用例

1. 字符串固定

2. 成对出现

3. 闭合顺序（最后出现的括号第一个闭合） => 最先出现的括号最后一个闭合

算法原理

1. 用栈模拟括号的顺序

2. 可以创建一个对象，建立左右括号的对应关系，key 为左括号，value 为右括号

算法流程

1. 遍历字符串的每一个字符

2. 如果是左括号，入栈

3. 如果是右括号，判断栈顶的第一个元素与当前右括号是否对应？如果不对应，就返回 false

4. 遍历完之后保证栈内为空