介绍

栈结构只能在栈顶插入或取出数据, 不能在任意位置插入数据

提示

插入数据也称为进栈/压栈/入栈

删除/取出数据也称为出栈/退栈

也就是后进先出(LIFOL: last in first out)

优点: 提供后进先出的存储方式, 添加速度快, 允许重复

缺点: 只能在一头操作数据, 存取其他项很慢

小测验

不是一次性压入这6个元素, 可以同时出或者入

A

压6, 压5, 出5, 压4, 出4, 压3, 出3, 出6, 压2, 压1, 出1, 出2

B

压6, 压5, 压4, 出4, 出5, 压3, 出3, 压2, 出2, 压1, 出1, 出6

C

压6, 压5, 压4, 压3, 出3, 出4,

出不来了, 因为需要先出5才能出6

D

压6, 压5, 压4, 压3, 压2, 出2, 出3, 出4, 压1, 出1, 出5, 出6

TS实现

  class Stack {
    #value: any[] = []

    push(val: any) {
      return this.#value.push(val)
    }
    pop() {
      return this.#value.pop()
    }
    peek() {
      return this.#value[this.#value.length - 1]
    }
    isEmpty() {
      return this.#value.length === 0
    }
    size() {
      return this.#value.length
    }
    toString() {
      return this.#value.toString()
    }
  }

案例

使用 栈 实现 十进制 转 二进制

  function dec2bin(number: number) {
    const stack = new Stack()
    while (number > 0) {
      stack.push(number % 2)
      number = Math.floor(number / 2)
    }

    let bin = ''
    while (!stack.isEmpty()) {
      bin += stack.pop()
    }
    return bin
  }