Frank
  • 数据结构与算法
大约 3 分钟约 833 字...

简介

  • 一个后进先出的数据结构
  • javaScript中没有栈,但可以用 Array 实现栈的所有功能
const stack = []
stack.push(1)
stack.push(2)
const item1 = stack.pop()
const item2 = stack.pop()

应用场景

需要后进先出的场景

十进制转二级制

除2取余,逆序排列

后出来的余数反而要排到前面 把余数依次入栈,然后再出栈,就可以实现余数倒序输出

个人思路:不用栈,直接把字符串反转open in new window

const tenToTwo = (num) => {
  const arr = []
  let remainNum
  while (num >= 1) {
    remainNum = num % 2
    // 向下取整
    num = Math.floor(num / 2)
    arr.push(remainNum)
  }
  return arr.reverse().join('')
}

判断字符串的括号是否有效

20.有效的括号open in new window

注意

可以使用字典 Map 优化算法

  • 解题思路 对于没有闭合的左括号而言,越靠后的左括号,对应的右括号越靠前;满足后进先出,考虑用栈。

  • 解题步骤

  1. 新建一个栈
  2. 遍历字符串,遇左括号入栈,遇到和栈顶括号类型匹配的右括号就出栈,类型不匹配直接判定为不合法。
  3. 最后栈空了就合法,否则不合法

用队列实现栈

225. 用队列实现栈open in new window

前端与栈:函数调用堆栈

  • JS解释器使用栈来控制函数的调用顺序

  • 最后调用的函数反而最先执行完

const fun1 = () => {
  fun2()
}
const fun2 = () => {
  fun3()
}
const fun3 = () => {}
fun1()

函数执行顺序 fun3() -> fun2() -> fun1()

上次编辑于:
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.1