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

栈和队列

⚡ 30 秒速记

• 栈是后进先出 LIFO，只操作同一端；队列是先进先出 FIFO，从尾部入队、从头部出队
• JavaScript 数组的 push() / pop() 适合栈；用 shift() 实现大队列会频繁搬移索引，应改用 head 指针或环形缓冲区
• 栈适合括号匹配、撤销、调用过程和单调栈；队列适合层序遍历、任务调度、消息缓冲和生产消费
• 判断空结构要基于有效元素数量，不能只看底层数组长度；带 head 指针的队列还需要周期性压缩
• 工程中的并发队列还要定义容量、背压、失败重试和关闭语义，数据结构正确不等于调度系统可靠

栈遵循后进先出，队列遵循先进先出，前端面试里通常都可以基于数组实现。 栈直接使用 push() 和 pop() 即可；队列若连续调用 shift()，剩余元素的索引会反复移动，所以更适合维护 head 指针。此时有效区间是 [head, items.length)，出队只递增指针，并在已消费空间足够大时批量压缩，均摊成本仍为 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 中，栈和队列的实现一般都要依赖于数组，大家完全可以把栈和队列都看作是“特别的数组”。

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