本节我们基于对数组的理解和掌握，围剿线性数据结构（栈、队列和链表）。

栈和队列

⚡ 30 秒速记

• 栈 = 后进先出 LIFO，只动一头；队列 = 先进先出 FIFO，尾进头出
• 栈直接 push + pop；队列别用 shift 扛大数据，维护 head 下标，出队只挪指针
• 栈的场景：括号匹配、撤销、函数调用、DFS、单调栈；队列：BFS / 层序遍历、任务调度
• 带 head 的队列，长度是 items.length - head，别直接看数组长度
• 真做任务队列还要定容量、满了怎么办（拒绝 / 等待 / 丢弃）、失败怎么重试

栈是后进先出，像一摞盘子只从顶上拿；队列是先进先出，像排队买饭先到先得。 在 JS 里两者都用数组模拟，栈直接 push 加 pop 就完了。队列按教科书写是 push 加 shift，但 shift 每次要把后面所有元素往前挪一位，BFS 跑一万个结点就是上千万次搬移。我一般给队列维护一个 head 下标，出队只把 head 加一，有效区间是 [head, items.length)，攒到一定量再批量 slice 一次，均摊下来还是 O(1)。

下面给出一个不会因连续 shift() 退化的队列。入队和出队的均摊时间都是 O(1)；当已消费空间超过一半时才批量压缩一次，避免底层数组无限增长。

class Queue {
  #items = []
  #head = 0

  enqueue(value) {
    this.#items.push(value)
  }

  dequeue() {
    if (this.size === 0) return undefined
    const value = this.#items[this.#head]
    this.#head += 1
    if (this.#head > 1024 && this.#head * 2 > this.#items.length) {
      this.#items = this.#items.slice(this.#head)
      this.#head = 0
    }
    return value
  }

  get size() {
    return this.#items.length - this.#head
  }
}

队列的不变量是有效区间始终为 [head, items.length)；dequeue() 只移动 head，不移动剩余元素。批量 slice() 单次是 O(n)，但不会每次出队都发生，所以连续操作的均摊成本仍是常数级。若队列必须限制内存，应额外设置容量，并让 enqueue() 在满时拒绝、等待或丢弃，三种策略必须由业务决定。

在 JavaScript 中，栈和队列的实现一般都要依赖于数组，大家完全可以把栈和队列都看作是“特别的数组”。

（注：实际上，栈和队列作为两种运算受限的线性表，用链表来实现也是没问题的。只是从前端面试做题的角度来说，基于链表来实现栈和队列约等于脱裤子放屁（链表实现起来会比数组麻烦得多，做不到开箱即用），基本没人会这么干。这里大家按照数组的思路往下走就行了）