#

后进先出

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

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

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

# 应用

# 函数调用

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

# 表达式求值

利用两个栈,一个保存操作数,另一个保存运算符。从左开始遍历表达式,当遇到数字,直接压入操作数栈。当遇到运算符,就与运算符栈的栈顶元素进行比较,若比栈顶元素的优先级高,就将当前运算符压入栈;否则,从运算符栈中取出栈顶运算符,从操作数栈中取出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
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24