原始讲解：https://labuladong.online/algo/data-structure-basic/cycle-array/

好的，教练来了！今天我们要把 Labuladong 讲的“循环数组”这个知识点，彻底转化为咱们 OIer 自己的肌肉记忆。

很多同学可能会觉得：“数组不就是 a[i] 吗，有什么好学的？” 但在算法竞赛中，能否将一个普通的线性数组“卷”起来用，是区分新手和老手的分水岭。掌握了它，你手写队列、理解单调队列、解决各种模拟题的能力都会上一个大台阶。

---

课件：循环数组——将一维空间卷成“甜甜圈”

一、引入：普通队列的“烦恼”

我们都知道，队列 (Queue) 是一个“先进先出” (FIFO) 的数据结构。如果用普通数组来模拟，通常需要两个指针：head 指向队头，tail 指向队尾。

• 入队 (Push)：q[tail++] = x;
• 出队 (Pop)：head++;

看起来很美好，但问题来了：随着不断地入队和出队，head 和 tail 指指针会一直向右移动。

初始:  [ H,T,  ,  ,  ,  ,  ]  (head=0, tail=0)
操作后: [  ,  ,  ,  , H,  , T]  (head=4, tail=6)

很快，tail 就会到达数组的末尾，即使数组前面有很多因为出队而空出来的空间，我们也无法再利用它们了。我们总不能每次 pop 都把整个队列的元素搬回数组开头吧？那样的操作就变成了 $O(N)$，在竞赛中是不可接受的。

核心矛盾：我们想复用数组前面的空间，但线性数组的下标是单向增长的。

解决方案：把数组的“尾巴”和“头”连起来，形成一个环——这就是循环数组。

二、核心思想：取模运算的魔法

如何把直的掰成弯的？靠的就是大家熟知的取模运算符 %。

想象一个容量为 capacity 的数组，下标从 0 到 capacity-1。我们希望当指针 i 到达 capacity-1 后，下一步能自动回到 0。

这个操作用数学公式表达就是： 下一个位置 = (当前位置 + 1) % capacity

举例 (capacity = 8)：

• 当前在 0，下一步是 (0 + 1) % 8 = 1。
• ...
• 当前在 6，下一步是 (6 + 1) % 8 = 7。
• 当前在 7，下一步是 (7 + 1) % 8 = 0。 $\leftarrow$ 魔法发生在这里！

就像一个时钟，11点过了是12点，12点过了又回到了1点。取模运算就是我们用来弯曲线性空间的数学工具。

三、实战一：手写一个高效的循环队列

现在，我们用循环数组的思想来重构队列。我们需要：

• 一个定长数组 q[CAPACITY]
• 队头指针 head
• 队尾指针 tail

1. head 和 tail 的定义

• head：指向队头元素的下标。
• tail：指向下一个可插入位置的下标。

2. 关键判定：判空与判满 这是一个经典问题。如果我们让 head 和 tail 在环上自由追逐（像在学校操场400米跑道上跑步套圈），当 head == tail 时，我们无法判断队列是空还是满。

• 空状态：head 追上 tail，队列为空。
• 满状态：tail 追上 head，队列已满。

为了区分这两种情况，我们有两种主流的解决方案：

方案	判空条件	判满条件	优点	缺点	教练建议
牺牲一格空间	head == tail	(tail + 1) % capacity == head	逻辑判断简洁，代码不易出错	浪费一个存储单元	竞赛首选
使用 size 变量	size == 0	size == capacity	空间利用率100%	需额外维护 size，多一步操作	在内存极度受限时考虑

在竞赛中，空间通常很充裕，用一点点空间换取代码的简洁和稳定，非常划算。我们接下来的模板将采用方案一。

3. OI 竞赛风格代码模板 (CircularQueue)

#include <iostream>

using namespace std;

// 定义一个较大的常量作为队列容量
// 竞赛中通常根据题目数据范围来定，比如 N=10^5，就开 100010
const int CAPACITY = 10; 

struct CircularQueue {
    int q[CAPACITY];
    int head;
    int tail;

    // 初始化
    void init() {
        head = 0;
        tail = 0;
    }

    // 判空
    bool empty() const { // 加 const 表示该函数不修改成员变量
        return head == tail;
    }

    // 判满（牺牲一个空间）
    bool full() const {
        return (tail + 1) % CAPACITY == head;
    }

    // 入队
    bool push(int x) {
        if (full()) {
            return false; // 队列已满
        }
        q[tail] = x;
        tail = (tail + 1) % CAPACITY; // tail 指针向后移动，并“卷起来”
        return true;
    }

    // 出队
    bool pop() {
        if (empty()) {
            return false; // 队列为空
        }
        head = (head + 1) % CAPACITY; // head 指针向后移动，并“卷起来”
        return true;
    }

    // 获取队头元素
    int front() const {
        // 实际比赛中，应保证非空时才调用
        return q[head];
    }
};

四、实战二：升级到双端队列 (Deque)

双端队列，顾名思义，就是队头队尾都能进行 push 和 pop 操作。这要求我们的指针不仅能向后移动，还能向前移动。

反向移动的“陷阱”与技巧

想当然地，我们可能会写 (index - 1) % CAPACITY。 这是错误的！ 在 C++ 中，当 index 为 0 时，0 - 1 = -1，-1 % CAPACITY 的结果是 -1 (或依赖于编译器的实现)，而不是我们期望的 CAPACITY - 1。

正确做法（竞赛必备技巧，利用模运算性质保证取模余数为正）： 上一个位置 = (当前位置 - 1 + CAPACITY) % CAPACITY

通过先加上 CAPACITY，我们保证了被取模的数永远是正数，从而得到正确的回绕效果。

OI 竞赛风格代码模板 (CircularDeque)

#include <iostream>

using namespace std;

const int DEQUE_CAPACITY = 10;

struct CircularDeque {
    int q[DEQUE_CAPACITY];
    int head;
    int tail;

    void init() {
        head = 0;
        tail = 0;
    }

    bool empty() const {
        return head == tail;
    }

    bool full() const {
        return (tail + 1) % DEQUE_CAPACITY == head;
    }

    // 从队尾入队
    bool push_back(int x) {
        if (full()) return false;
        q[tail] = x;
        tail = (tail + 1) % DEQUE_CAPACITY;
        return true;
    }
    
    // 从队头入队
    bool push_front(int x) {
        if (full()) return false;
        // head 指针向前移动
        head = (head - 1 + DEQUE_CAPACITY) % DEQUE_CAPACITY;//减法需要处理保证取模后非负
        q[head] = x;
        return true;
    }

    // 从队头出队
    bool pop_front() {
        if (empty()) return false;
        head = (head + 1) % DEQUE_CAPACITY;//加法肯定不为负无需特殊处理，虽然按特殊处理写法也没错
        return true;
    }

    // 从队尾出队
    bool pop_back() {
        if (empty()) return false;
        // tail 指针向前移动
        tail = (tail - 1 + DEQUE_CAPACITY) % DEQUE_CAPACITY;
        return true;
    }

    int front() const {
        return q[head];
    }

    int back() const {
        // 注意：tail 指向的是下一个可插入位置，所以队尾元素在 tail 前一个位置
        int last_element_idx = (tail - 1 + DEQUE_CAPACITY) % DEQUE_CAPACITY;
        return q[last_element_idx];
    }
};

main函数测试部分略，可参考上一个模板自行测试。

五、应用场景与进阶思考

1. BFS (广度优先搜索)：在图论和搜索问题中，BFS需要一个队列来维护待访问的节点。手写一个高效的循环队列是基本功。
2. 滑动窗口最值 (单调队列)：单调队列的底层实现就是一个双端队列(deque)，而循环数组是实现双端队列的基础。
3. 各种模拟题：涉及到周期性、循环、排队等场景的题目，循环数组都是非常有力的工具。
4. 约瑟夫问题：经典的约瑟夫环问题，可以用循环数组或循环链表来高效模拟。

教练总结

1. 核心是取模 %：它能将线性空间在逻辑上变成环形。
2. 反向移动公式要背熟：(idx - 1 + capacity) % capacity，这是避免负数取模问题的标准解法。
3. 判空判满是关键：牺牲一个空间 ((tail + 1) % capacity == head) 是竞赛中最稳妥、最简洁的判满方法。
4. 不要害怕造轮子。虽然 C++ STL 提供了 std::queue 和 std::deque，但在某些需要更高性能或更底层控制的场合（比如单调队列优化DP），手写循环数组能让你对程序的掌控力更强，且通常比STL更快。

掌握循环数组，你就掌握了在有限空间里“无限”腾挪的技巧。快去练习一下吧！

---

这是一个非常经典的入门级练习题，它考察了循环数组中最核心的两个点：下标越界的回绕（正向）和负数下标的处理（反向）。

---

课后练习题：环状序列的游走

【题目描述】

有一个长度为 $N$ 的整数序列 $A = [A_0, A_1, \dots, A_{N-1}]$，这些数被首尾相连摆放成一个圆环。也就是说，$A_{N-1}$ 的下一个元素是 $A_0$，而 $A_0$ 的前一个元素是 $A_{N-1}$。

我们要在这个环上进行一次“游走”。 初始时，你站在下标为 $0$ 的位置（即元素 $A_0$ 处）。 接下来会依次给出 $M$ 个移动指令。对于每个指令 $k$：

• 如果 $k > 0$，表示你需要沿顺时针方向（下标增加的方向）移动 $k$ 步。
• 如果 $k < 0$，表示你需要沿逆时针方向（下标减小的方向）移动 $|k|$ 步。

请你计算出执行完所有 $M$ 个指令后，最终你所停留位置上的数值是多少。

【输入格式】

第一行包含两个正整数 $N$ 和 $M$，分别表示序列长度和指令数量。 第二行包含 $N$ 个整数，表示环状序列 $A_0, A_1, \dots, A_{N-1}$。 第三行包含 $M$ 个整数，表示依次执行的移动指令 $k_1, k_2, \dots, k_M$。

【输出格式】

输出一个整数，表示最终停留位置上的数值。

【样例输入】

5 4
10 20 30 40 50
2 -1 4 -2

【样例输出】

40

【样例解释】

1. 起点下标 0。
2. 走 +2 步 -> 下标 2。
3. 走 -1 步 -> 下标 1。
4. 走 +4 步 -> 下标 5，即下标 0。
5. 走 -2 步 -> 从 0 倒退 2 步，变成 4，再变成 3。最终停在下标 3，对应数值 40。

【数据范围】

• $1 \le N, M \le 100$
• $-100 \le k \le 100$ (注意 $k$ 可能是负数)
• $1 \le A_i \le 1000$

---