跳至主要內容

zfh大约 3 分钟约 852 字

简介

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

应用场景

需要后进先出的场景

十进制转二级制

除2取余,逆序排列
除2取余,逆序排列

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

JS
const tenToTwo = (num) => {
  const stack = []
  let remainNum
  while (num >= 1) {
    remainNum = num % 2
    // 向下取整
    num = Math.floor(num / 2)
    stack.push(remainNum)
  }
  let str = ``
  while (stack.length > 0) {
    str += stack.pop()
  }
  return str
}

个人思路:不用栈,直接把字符串反转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. 最后栈空了就合法,否则不合法
JS
/*
 * @lc app=leetcode.cn id=20 lang=javascript
 *
 * [20] 有效的括号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  if (s.length < 2) return false
  const stack = []
  const map = new Map()
  map.set('{', '}')
  map.set('(', ')')
  map.set('[', ']')
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      stack.push(s[i])
    } else {
      let top = stack[stack.length - 1]
      if (s[i] === map.get(top)) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
}
// @lc code=end

用队列实现栈

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

s JS
/*
 * @lc app=leetcode.cn id=225 lang=javascript
 *
 * [225] 用队列实现栈
 */

// @lc code=start

var MyStack = function () {
  this.queue = []
}

/**
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function (x) {
  return this.queue.push(x)
}

/**
 * @return {number}
 */
MyStack.prototype.pop = function () {
  return this.queue.pop()
}

/**
 * @return {number}
 */
MyStack.prototype.top = function () {
  return this.queue[this.queue.length - 1]
}

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function () {
  return this.queue.length === 0
}

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */
// @lc code=end

前端与栈:函数调用堆栈

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

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

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

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

上次编辑于:
本站勉强运行 小时