栈和队列的基本应用详解编程语言

栈的使用

给定一个字符串,只包含{,[, (,),],},判断字符串的括号匹配是否合法。如(),()[]{}是合法的,而(]是不合法的
假设一个字符串’{[()]}’,当我们遍历时遇到左操作符的时候,就将它压入栈中,当遇到右操作符的时候,就与栈顶的元素匹配,如果match就将栈顶的左操作符弹出,继续遍历。如果没有match的话就返回false。如果遍历结束的时候栈也为空,这个字符就是合法的。

   function isValid(str){ 
      for(var i = 0, len = str.length; i < len; i++){ 
         if(str[i] == '(' || str[i] == '{' str[i] == '[' ){ 
            stack.push(str[i]) 
         } else { 
            if(stack.size == 0) return false; 
            var c = stack.pop(); 
            //省略match定义 
            if(!str[i].match(c)){  
               return false; 
            } 
         } 
      } 
      if(stack.size == 0) { 
         return true; 
      } else { 
         return false; 
      } 
   }

栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素

栈和递归的紧密关系

我们先看一下二叉树的先序遍历

   function preorder(node){ 
      if(node){ 
         console.log(node.value); 
         preorder(node.left); 
         preorder(node.right); 
      } 
   }

我们来看一下具体的遍历,假设我们只有三个节点,父节点是1,左节点是2,右节点是3。我们首先使用根节点调用函数preorder,然后使用节点2调用了函数preorder,再使用节点3调用了函数preorder。这三次preorder的传入参数是不同的,那么这三个函数的调用顺序是怎么样的?我们可以抽象为根节点调用时,执行到节点2调用的时候停住了,接着执行一个子函数也就是节点2的调用,直到节点2调用结束之后,再进行节点3子函数的调用。那么操作系统就是通过栈来实现这样一个操作。根节点调用的函数先被压入栈中开始执行,这时遇到了函数栈节点2。在节点2的函数被压入栈之后立即执行,等到执行完之后返回值(或不返回),然后节点2的函数被弹出。节点2的函数被弹出之后,节点1的函数继续执行,节点3的函数被压入并立即执行。

队列的基本应用

队列比较常用的是广度优先遍历,在树中是层序遍历,在图中是无权图的最短路径
我们来看一下二叉树的层序遍历

    var node; 
    levelOrder(root){ 
       var result = []; 
       if(root == null) return result; 
       queue.push(root); 
       while(!queue.empty()){ 
           var node = queue.front(); 
           if(node.left) queue.push(node.left); 
           if(node.right) queue.push(node.right); 
       result.push(node.value); 
       } 
    }

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/13481.html

(0)
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论