栈与队列

栈(stack):后进先出(LIFO-last in first out):最后插入的元素最先出来。

队列(queue):先进先出(FIFO-first in first out):最先插入的元素最先出来。

示例:

有效的括号:力扣20

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

对括号的有效性判断,现实中也很常⻅,⽐如说我们写的代码,编辑器会检查括号是否正确闭合。⽽且我们的代码可能会包含三种括[](){},判断起来有⼀点难度。

我们遍历给定的字符串。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串无效,返回False

function isValid(str){
    var stack = [];
    var stackTop; //栈顶元素
    for(var i = 0;i<str.length;i++){
        var cur = str[i]; // 当前遍历的括号
        //遇到左括号,就把对应的右括号放入栈中
        if(cur=='{'){
            stack.push('}')
        }else if(cur=='('){
            stack.push(')')
        }else if(cur=='['){
            stack.push(']')
        }else{
            // 遇到的是右括号
            stackTop = stack.pop(); // 取出栈顶括号,也就是最近一次遇到的 左括号的(对应括号)
            //如果此时遍历的右括号,跟从栈中取出的括号不同,就直接false
            //相同,就继续往下遍历
            if(stackTop!==cur){
                return false
            }
        }
    }
    // return stack.length==0
    // 栈中无元素说明 完全匹配(括号有效)
    return !stack.length;
}
文档更新时间: 2022-04-27 17:40   作者:张老师