基础数据结构

环形数组

一个取模就成环

环形数组不是一种新的数据结构，就是普通数组 + 下标取模：

const next = (i, n) => (i + 1) % n;

走到 n-1 再往前一步，n % n === 0，回到开头。

它解决的是「首尾相接」这一类需求：约瑟夫环、轮转调度， 以及最重要的 —— 让数组高效地当队列用。

🚨 JavaScript 的 % 是「取余」，不是「取模」

往回走一步的时候，坑就来了：

const prev = (i, n) => (i - 1) % n;   // ❌ i = 0 时得到 -1

数学上的取模结果永远非负，但 C 系语言（含 JS、Java、C++）的 % 是取余， 符号跟着被除数走：

-1 % 5 = -1        （不是 4）
-6 % 5 = -1        （不是 4）

正确写法要先加一个 n 再取一次模：

const prev = (i, n) => ((i - 1) % n + n) % n;   // ✅ i=0, n=5 → 4

⚠️ 为什么外面还要再取一次 % n？因为这个式子也要能处理非负的输入。 i % n 已经非负时，+ n 会把它顶出范围：

i=-1  n=5:  i%n=-1  →  +n=4  →  %n=4      ✅ +n 就够了
i=-5  n=5:  i%n= 0  →  +n=5  →  %n=0      ← +n 越界，外层救回来
i= 7  n=5:  i%n= 2  →  +n=7  →  %n=2      ← 同上

⭐ 所以外层那个 % n 不是为了「负得不够多」，而是为了让同一个式子对正负输入都成立。 写通用工具函数时省不得；如果你能确定输入永远是 -1（只后退一步），单加一个 n 确实够。

🚨 症状是 arr[-1]。JavaScript 里这不报错，返回 undefined —— 于是错误会一路飘到很远的地方才炸，报的还是别的错。 Python 的 % 反而是数学取模（-1 % 5 == 4）， 所以从 Python 换过来的人特别容易踩这一个。

📌 记法：只往前走可以直接 % n；只要有可能往回走，就用那个双取模的写法。

环形数组实现队列

链表那篇说过，数组头部删除是 O(n)。 所以用数组做队列时，shift() 会让整体退化到 O(n²) —— 层序遍历里提过这一点， 当时的对策是「用下标当队头、不真删」。

那个办法的代价是数组只增不减。环形数组是它的定容版本： 空间固定，头尾都靠取模绕回来。

class CircularQueue {
  constructor(capacity) {
    // 🚨 多留一格：见下方「怎么区分空和满」
    this.data = new Array(capacity + 1);
    this.cap = capacity + 1;
    this.head = 0;
    this.tail = 0;          // tail 指向「下一个要写入的位置」
  }

  get size() { return (this.tail - this.head + this.cap) % this.cap; }
  get isEmpty() { return this.head === this.tail; }
  get isFull() { return (this.tail + 1) % this.cap === this.head; }

  push(x) {
    if (this.isFull) return false;
    this.data[this.tail] = x;
    this.tail = (this.tail + 1) % this.cap;
    return true;
  }

  shift() {
    if (this.isEmpty) return undefined;
    const x = this.data[this.head];
    this.head = (this.head + 1) % this.cap;
    return x;
  }
}

🚨 怎么区分「空」和「满」

这是环形队列唯一真正的难点。

head === tail 时，队列可能是空的，也可能是满的 —— 转了一整圈回到原点。 两种完全相反的状态给出同一个信号。

三种解法，各有取舍：

办法 代价
牺牲一格（上面用的） 少存一个元素，逻辑最简单
额外存一个 size 计数 每次增删都要维护它
存一个 isFull 标志 同上，且容易忘记更新

⭐ 牺牲一格的判据是 (tail + 1) % cap === head —— 即「再写一个就要撞上队头了」。所以构造时要 capacity + 1， 否则用户要 5 个格子，实际只能存 4 个。

⚠️ 忘记 +1 的症状：容量永远比声明的少一个。 小数据下完全看不出来（谁会正好装满），压测才暴露。

约瑟夫环

题意：n 个人围成一圈，从第 1 个开始报数，每数到第 k 个就出局，问最后剩下谁。

直接模拟是 O(n·k)。但换个角度看，它有个 O(n) 的递推：

function josephus(n, k) {
  // f(i) = i 个人时，幸存者在「当前这一圈」里的下标（0-indexed）
  let pos = 0;                       // f(1) = 0：只剩一个人，他就在 0 号位
  for (let i = 2; i <= n; i++) {
    pos = (pos + k) % i;             // 每多一个人，起点往后挪 k
  }
  return pos;                        // 0-indexed；题目要 1-indexed 就 +1
}

⭐ 递推的含义：i 个人的问题，出局一个之后就变成 i-1 个人的问题， 只是起点挪了 k 位。把 i-1 的答案往回映射，就是 (pos + k) % i。

📌 不用记推导 —— 记住「约瑟夫环有个一行的递推」就够了， 面试里能说出这句话，比现场推公式实际得多。

下一步

队列讲到这里，栈与队列那篇接着讲它们的变形 —— 其中单调栈和单调队列是两个覆盖面很广的技巧。

练习

勾选记录做过哪些，0 / 4 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。