算法 - 栈类型

栈

• 一个后进先出的数据结构
• javascript中没有栈，但可以用Array实现栈的所有功能

栈的应用场景

• 需要后进先出的场景
• 比如：十进制转二进制、判断字符串的括号是否有效、函数调用堆栈……

二进制

二进制

• 后出来的余数反而要排到前面
• 把余数依次入栈，然后再出栈，就可以实现余数倒叙输出

有效的括号

leeCode第20题

• 越靠后的左括号，对应的右括号越靠前
• 左括号入栈，右括号出栈，最后栈空了就是合法的

该系列并没有完全按照官方答案或参考他人答案，纯粹自己实现。本人并不纠结于是否有更好的实现，纯粹学习思路，毕竟前端算法除了面试基本也用不上了。花过多精力并不值得

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function(s) {
    const stack = []
    const signDict = {
        '}': '{',
        ')': '(',
        ']': '['
    }
    const leftSign = ['(', '{', '[']
    const rightSign = [')', '}', ']']

    if (s.length % 2) return false

    for (let i = 0; i < s.length; i++) {
        const str = s[i]
        const isLeftSign = leftSign.includes(str)
        const isRightSign = rightSign.includes(str)

        if (isLeftSign) stack.push(str)
        if (isRightSign) {
            const lastSign = stack.pop()
            return lastSign === signDict[str]
        }
    }

    if (stack.length) return false
}