栈

后进先出

从栈的操作特性来看，是一种“操作”受限的新线性表，只允许在端插入和删除数据。

用数组和链表均可实现，虽然数组和链表使用起来灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。

当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，应该首选栈这种数据结构。

应用

函数调用

每进入一个函数，就会将其中的变量作为栈帧入栈，当调用函数执行完成后，将这个函数对应的栈帧出栈。

表达式求值

利用两个栈，一个保存操作数，另一个保存运算符。从左开始遍历表达式，当遇到数字，直接压入操作数栈。当遇到运算符，就与运算符栈的栈顶元素进行比较，若比栈顶元素的优先级高，就将当前运算符压入栈；否则，从运算符栈中取出栈顶运算符，从操作数栈中取出2个操作数，进行计算，把计算完的结果压入操作数栈，继续比较。

括号匹配（如：([{}])）

用栈保存未匹配的左括号，从左到右扫描字符串。当扫描到左括号，则压入栈中；当扫描到右括号，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。扫描过程中，遇到不能配对或栈中没有数据，则说明为非法格式。当扫描完成之后，如果栈为空，则合法；否则，非法格式。

浏览器的前进后退功能

使用两个栈X和Y，首次浏览的页面依次压入栈X，当点击后退按钮时，从栈X取出压入栈Y。当点击前进按钮时，从栈Y取出压入栈X。访问其他页面时，除了压入栈X以外，还需要清空栈Y。

习题

有效的括号（Topic：Lc20 (opens new window)）

代码实现

var isValid = function (s) {
    const sym = {
        '(': ')',
        '{': '}',
        '[': ']'
    }

    const res = []

    for(let i = 0,len = s.length; i < len; i++) {
        const t = s[i]
        if (sym[t]) {
            res.push(t)
        } else {
            if (t !== sym[res.pop()]) {
                return false
            }
        }
    }
    if (res.length) {
        return false
    }
    return true
};