幻空博客

外观

栈

复制页面

约 293 字小于 1 分钟

2023-11-21

介绍

image-20231121135308590

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

提示

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

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

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

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

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

小测验

image-20231121141957632

不是一次性压入这 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
}