栈的使用
给定一个字符串,只包含{,[, (,),],},判断字符串的括号匹配是否合法。如(),()[]{}是合法的,而(]是不合法的
假设一个字符串’{[()]}’,当我们遍历时遇到左操作符的时候,就将它压入栈中,当遇到右操作符的时候,就与栈顶的元素匹配,如果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