FILO
后进先出

模拟栈

// 模拟栈
class Stack {
    constructor() {
        this.stk = [];
        this.top = -1;
    }
    push(n) {
        this.stk[++this.top] = n;
    }
    pop() {
        if (this.top === -1) return;
        this.top--;
        this.stk.pop()
    }
    topN() {
        return this.top === -1 ? 0 : this.stk[this.top];
    }
    size() {
        return this.top - 1;
    }
    isEmpty() {
        return this.top === -1;
    }
}
const stk = new Stack();
stk.push(1);
stk.push(2);
stk.push(3);
console.log(stk);
stk.pop();
console.log(stk);
console.log(stk.size());
console.log(stk.topN());

题目

lc20：括号匹配

1. 使用一个hash结构，map保存对应括号
2. 维护一个栈，将左括号入栈
3. 依次出栈括号，出栈的括号必须得和右括号匹配，否则直接返回false
4. 最后栈为空才算true

lc144：二叉树的前序遍历

1. 维护一个栈，按照：根节点-右子节点-左子节点的顺序入栈
2. 利用一个循环判断树是否遍历完毕

var preorderTraversal = function(root) {
    const res = [];
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const n = stack.pop();
        res.push(n.val);
        n.right && stack.push(n.right)
        n.left && stack.push(n.left);
    }
    return res;
};

lc94：二叉树的中序遍历

1. 按照根节点-左子节点顺序入栈
2. 左子节点入栈完成后，依次出栈保存出栈结点并入栈右子结点
3. 循环第1步

   var inorderTraversal = function (root) {
    const res = []
    const stk = [];
    let p = root;
    while(stk.length || p) {
        while(p) {
            stk.push(p);
            p = p.left;
        }
        const last = stk.pop();
        res.push(last.val);
        p = last.right;
    }
    return res;
   };