栈和队列

一、是什么

使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；

使用队列存储数据，讲究 “先进先出”，即最先进队列的数据，也最先出队列。

二、例题

1、逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例： :::info 输入：tokens = [“2”,”1”,”+”,”3”,”“]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 :::

思路

提前声明运算符对应的运算函数，将数字放进栈中，遇到运算符的时候将栈顶的两个数字提取出来做运算，然后再将运算结果存入栈中。
最后栈中存在唯一元素，即为结果。

let evalRPN = function (tokens) {
  let stack = []
  for (let token of tokens) {
    let op = opMap[token]
    if (op) {
      let a = parseInt(stack.pop())
      let b = parseInt(stack.pop())
      let res = op(a, b)
      stack.push(res)
    } else {
      stack.push(token)
    }
  }
  return stack[0]
}
let opMap = {
  "+": (a, b) => b + a,
  "-": (a, b) => b - a,
  "*": (a, b) => b * a,
  "/": (a, b) => parseInt(b / a, 10),
}

2.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例： :::info 输入：s = “()” 输出：true
输入：s = “(]” 输出：false :::

思路

先通过哈希表建立括号间的映射关系，然后将左括号放入栈中。当遇到右括号时，判断是否与栈顶元素形成映射，若是则出栈，若否则直接返回false.

var isValid = function(s) {
    const len = s.length
    if (len === 1) return false
    const map = new Map()
    map.set('(', ')')
    map.set('{', '}')
    map.set('[', ']')
    // 栈先存进一个元素，避免删除栈顶元素时报错
    const stack = ['?']
    for (let i of s) {
        if (map.has(i)) {
            stack.push(i)
        } else {
            let tmp = stack[stack.length-1]
            if (map.get(tmp) === i) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return stack.length === 1 ? true : false
};

3、二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例： :::info 输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <—-
/ \
2 3 <—-
\ \
5 4 <—- :::

思路

基本还是通过二叉树 BFS 的方法进行解决即可，只是在取值的时候每一层都去最右边的值，也就是从左到右遍历的时候记录到的最后一个值即可。

var rightSideView = function(root) {
    const res = []
    if (!root) return res
    const queue = [root]
    while (queue.length) {
        let len = queue.length
        let last
        for (let i = 0; i < len; i++) {
            const node = queue.shift()
            if (node.left) {
                queue.push(node.left)
            } 
            if (node.right) {
                queue.push(node.right)
            }
            if (node.val !== 'undefined') {
                last = node.val
            }
        }
        res.push(last)
    } 
    return res
};