栈（stack）是一种遵循先入后出逻辑的线性数据结构。

我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。

我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

1.基于数组的实现

/* 基于数组实现的栈 */
class ArrayStack {
  #stack
  constructor() {
    this.#stack = []
  }

  /* 获取栈的长度 */
  get size() {
    return this.#stack.length
  }

  /* 判断栈是否为空 */
  isEmpty() {
    return this.#stack.length === 0
  }

  /* 入栈 */
  push(num) {
    this.#stack.push(num)
  }

  /* 出栈 */
  pop() {
    if (this.isEmpty()) throw new Error('栈为空')
    return this.#stack.pop()
  }

  /* 访问栈顶元素 */
  top() {
    if (this.isEmpty()) throw new Error('栈为空')
    return this.#stack[this.#stack.length - 1]
  }

  /* 返回 Array */
  toArray() {
    return this.#stack
  }
}

2.基于链表的实现

/* 基于链表实现的栈 */
class LinkedListStack {
  #stackPeek // 将头节点作为栈顶
  #stkSize = 0 // 栈的长度

  constructor() {
    this.#stackPeek = null
  }

  /* 获取栈的长度 */
  get size() {
    return this.#stkSize
  }

  /* 判断栈是否为空 */
  isEmpty() {
    return this.size === 0
  }

  /* 入栈 */
  push(num) {
    const node = new ListNode(num)
    node.next = this.#stackPeek
    this.#stackPeek = node
    this.#stkSize++
  }

  /* 出栈 */
  pop() {
    const num = this.peek()
    this.#stackPeek = this.#stackPeek.next
    this.#stkSize--
    return num
  }

  /* 访问栈顶元素 */
  peek() {
    if (!this.#stackPeek) throw new Error('栈为空')
    return this.#stackPeek.val
  }

  /* 将链表转化为 Array 并返回 */
  toArray() {
    let node = this.#stackPeek
    const res = new Array(this.size)
    for (let i = res.length - 1; i >= 0; i--) {
      res[i] = node.val
      node = node.next
    }
    return res
  }
}

3.应用

• 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会对上一个网页执行入栈，这样我们就可以通过后退操作回到上一个网页。后退操作实际上是在执行出栈。如果要同时支持后退和前进，那么需要两个栈来配合实现。
• 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会不断执行出栈操作。