JS数据结构与算法入门(二) - 数据结构之“栈”

梦里梦外; 2022-11-28 15:18 280阅读 0赞

## 1. 栈是什么? ##

一个后进先出的数据结构  
JS中没有栈, 但可以用Array实现栈的所有功能  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]

const stack = []
    stack.push(1);
    stack.push(2);
    const itme1 = stack.pop();
    const itme2 = stack.pop()

## 2. 什么场景下用栈? ##

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

1.  十进制转二进制  
    ![十进制转二进制][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center 1]  
    100011 后出来的余数反而要排到前面  
    把余数依次入栈, 然后再出栈, 就可以实现余数倒序输出

--------------------

1.  有效的括号  
    ![有效的括号][20200818165356397.png_pic_center]  
    越靠后的左括号, 对应的右括号越靠前  
    左括号入栈, 右括号出栈, 最后栈空了就是合法

力扣20  
解题步骤:

1.  新建一个栈数据结构
2.  扫描字符串, 也就是遍历每一个字符, 遇到左括号入栈, 遇到和栈顶括号(数组中最后一个推入的)类型匹配的右括号就出栈, 类型不匹配直接判定不合法. 最后栈空了就合法, 否则不合法

/** * @param {string} s * @return {boolean} */
    var isValid = function(s) { 
        if(s.length % 2 === 1) {  return false }
        const stack = [];
        for(let i = 0; i < s.length; i +=1 ) { 
            const c = s[i];
            if(c === '(' || c === '{' || c === '[') { 
                stack.push(c)
            } else { 
                const t = stack[stack.length - 1]
                if (
                    (t==='(' && c === ')') ||
                    (t==='{' && c === '}') ||
                    (t==='[' && c === ']')
                ) { 
                    stack.pop();
                } else { 
                    return false;
                }
            }
        }
        return stack.length === 0;
    };
    // 可以用字典数据结构优化
    // 时间复杂度: 有一个for循环, 而且里面也没有for循环了, 所有操作都是O1的复杂度, 所以时间复杂度On, O是length也就是字符串的长度
    // 空间复杂度: 新建了临时变量stack, stack在极端情况把s所有的字符都push进去, 该情况而言stack可能占用n个内存单元, n就是s的length, 所以空间复杂度也是On

--------------------

## 3. 前端与栈: JS中的函数调用堆栈? ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/ba814e0506fd41fcbe2e810d7b94b4de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/7269f563f9f44407b9a18d7254a52b8a.png
[20200818165356397.png_pic_center]: /images/20221124/7f1bf11582474effa00fe1fb636414fd.png