栈

简介

• 一个后进先出的数据结构
• javaScript中没有栈，但可以用 Array 实现栈的所有功能

const stack = []
stack.push(1)
stack.push(2)
const item1 = stack.pop()
const item2 = stack.pop()

应用场景

需要后进先出的场景

十进制转二级制

除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
}

TS

const tenToTwo = (num: number): string => {
  const stack: number[] = []
  let remainNum: any
  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
}

个人思路：不用栈，直接把字符串反转

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.有效的括号

::: warning 注意 可以使用字典 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

TS

/*
 * @lc app=leetcode.cn id=20 lang=typescript
 *
 * [20] 有效的括号
 */
// @lc code=start
function isValid(s: string): boolean {
  if (s.length % 2 !== 0) return false
  let stack: Array<string> = []
  let map: Map<string, string> = 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. 用队列实现栈

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

s TS

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

// @lc code=start
class MyStack {
  private queue: Array<number>
  constructor() {
    this.queue = []
  }

  push(x: number): void {
    this.queue.push(x)
  }

  pop(): number {
    return (this.queue as any).pop()
  }

  top(): number {
    return this.queue[this.queue.length - 1]
  }

  empty(): boolean {
    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()