 压到 O(1))
Hello 算法 ArrayQueue 源码解析：一个取余号，把出队从 O(n) 压到 O(1)
【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo
本文取材于《Hello 算法》仓库中的 array_queue.py 与 array_queue.md 可视化文件，并对照 queue.md 章节正文与多语言实现，完整拆解基于环形数组实现的手写队列：朴素数组为什么不够、取余号怎么让指针回绕、多语言版本如何同构、以及教学版离生产级还差哪些环节。
先算一笔账：朴素数组队列到底慢在哪
假设医院门诊系统要把当日号源按叫号顺序排队：新号从队尾追加，叫号从队头逐个发出。这是典型的"先入先出"场景，最直觉的实现就是一根数组加两个变量——front指向队首、rear指向队尾：
# 朴素版：数组当队列（反面教材） arr = [17, 23, 5, 42, 8] front, rear = 0, 4 # 出队：front 后移一格，看似 O(1) front = front + 1 # 但很快你会发现：front 一路右移，数组左侧全是"假空位" # 为了不浪费空间，每次出队后把剩余元素整体左移一格 for i in range(front, rear): arr[i - 1] = arr[i]你会发现这里有个绕不开的矛盾：front只增不减，队首元素出队后留下的空位永远用不上；而一旦不左移，rear顶到数组右端后，哪怕左边空了一半，队列也"满"了——这就是假满。为了让空位真正可用，每次出队都不得不对剩余元素做一次 O(n) 的整体搬移。换言之，入队是 O(1)、出队退化成 O(n)，而叫号场景里出队的频率显然不低于入队。
ArrayQueue的整套设计，本质上就是在回答一个问题：能不能不搬移元素，就让指针用满整段数组？答案是两个变量加一条取余公式，下面先看效果。
跑一遍仓库版 ArrayQueue，先看运行效果
在动手拆解之前，建议先把仓库里的正式源文件跑起来，心里有张"目标图"。该文件可直接执行：
python3 codes/python/chapter_stack_and_queue/array_queue.py实际输出（已在本机验证）：
队列 queue = [1, 3, 2, 5, 4] 队首元素 peek = 1 出队元素 pop = 1 出队后 queue = [3, 2, 5, 4] 队列长度 size = 4 队列是否为空 = False 第 0 轮入队 + 出队后 queue = [2, 5, 4, 0] 第 1 轮入队 + 出队后 queue = [5, 4, 0, 1] 第 2 轮入队 + 出队后 queue = [4, 0, 1, 2] ... 第 9 轮入队 + 出队后 queue = [6, 7, 8, 9]最后十行最值得看：容量只有 10 的队列，经过"入队 + 出队"交替十轮后，元素在数组里从右往左"绕"了一圈，却始终没有浪费一个槽位。这个"绕"字，就是全文的主角。如果你希望逐帧观察每一步_front、_size的内存变化，可以打开仓库内配套的 array_queue.md，它内嵌了 PythonTutor 可视化链接，点击 Forward 即可单步执行。
搭起设计骨架：三个变量与一条回绕公式
先给设计蓝图。整套实现只依赖三个成员变量和一条核心公式：
| 成员 / 方法 | 角色定位 | 关键行为 |
|---|---|---|
_nums | 环形"容器" | 长度在构造时定死，存元素的下标必须配合取余 |
_front | 队首指针 | 始终指向队首元素所在下标，出队时自增回绕 |
_size | 队列长度 | 记录有效元素个数，入队 +1、出队 -1，兼作满/空判据 |
push(num) | 入队 | 现算队尾下标 → 写入_nums→_size加一 |
pop() | 出队 | 读出队首 →_front自增回绕 →_size减一 |
peek() | 读队首 | 直接返回_nums[_front]，空队列抛异常 |
to_list() | 打印辅助 | 从_front起顺逻辑顺序读回真实列表 |
核心公式只有一条，全文所有回绕都从这里出发：
rear = (front + size) % capacity白话解释一下：front + size是"队首往后数 size 格"的绝对位置，它可能越过数组右端；% capacity（取余）把越界的部分折叠回数组左侧。数组因此被"接"成了一个圈，左侧那些朴素版永远用不上的空位，从此成为新元素的合法落点。
细节提醒：你可能期待看到第四个成员变量_rear——仓库版故意没有。队尾下标每次都用_front + _size现算，而不是单独维护一个指针。少存一个变量，就少了一类"两个指针不同步"的 bug，这是教学实现里很划算的取舍。
逐行拆 push 与 pop：O(1) 出队从哪来
下面把入队与出队两段完整代码摊开（已核对 array_queue.py 原文）：
def push(self, num: int): """入队""" if self._size == self.capacity(): # 判满：元素数 == 容量 raise IndexError("队列已满") # 现算队尾下标：越过右端就取余回到左侧（核心公式） rear: int = (self._front + self._size) % self.capacity() self._nums[rear] = num # 写入槽位 self._size += 1 # 长度加一 def pop(self) -> int: """出队""" num: int = self.peek() # 读出队首元素 # 队首指针右移一格：越过尾部则取余回到数组头部（同一公式） self._front = (self._front + 1) % self.capacity() self._size -= 1 # 长度减一 return num对照朴素版再算一次账：入队是一次取余 + 一次数组写入，出队是一次取余 + 一次赋值，全程没有任何元素搬移，两者都是 O(1)。O(1) 的来源不是"数组访问快"（朴素版也有），而是"不再需要为了腾空位而移动数据"。
细节提醒：to_list()里那行res[i] = self._nums[(j % self.capacity())]，j从_front起每轮 +1，理论上只需在越过右端时处理一次；这里选择每轮都取余，是拿一点点常数时间换"代码里看不出特例"的清晰度——教学代码经常这样偏保守。
对照四种语言：同一套骨架怎么写
同一份"三变量 + 取余"设计在仓库里至少铺到了十余种语言，挑几份有代表性的：
- Python 版：codes/python/chapter_stack_and_queue/array_queue.py
- Go 版：codes/go/chapter_stack_and_queue/array_queue.go
- JavaScript 版：codes/javascript/chapter_stack_and_queue/array_queue.js
- Java 版：codes/java/chapter_stack_and_queue/array_queue.java
- C++ 版：codes/cpp/chapter_stack_and_queue/array_queue.cpp
拿 Go 版 和 Python 版并排看，同构点一目了然：
func (q *arrayQueue) push(num int) { if q.queSize == q.queCapacity { // 满时静默 return（与 Python 的 raise 不同） return } rear := (q.front + q.queSize) % q.queCapacity // 同一条核心公式 q.nums[rear] = num q.queSize++ }rear := (q.front + q.queSize) % q.queCapacity与 Python 里的rear = (self._front + self._size) % self.capacity()逐字对应；差异只在语言习惯——Go 结构体字段不加下划线前缀，容量单独存了queCapacity字段，而 Python/Java 用len(nums)现算。再往细里看有一处值得注意的教学取舍：队列已满时，Python 版raise IndexError("队列已满")，Go 版和 Java 版则是打印一句后return，把入队悄悄吞掉。后者对演示友好，但在真实业务里是危险的默认行为，迁移到生产代码时应改为返回错误或扩容。
认清边界：教学版队列离生产还差什么
跑通之后再看三处"刻意的简陋"，它们正是手写队列走向生产级的三个关卡：
- 容量写死。
__init__里[0] * size一次性分配后不再变化，满了就只能抛错。queue.md 正文在末尾点明了解法：把底层换成动态数组并引入扩容机制——复制旧数组、按新容量重新定位front/size，有兴趣完全可以照着练手。 - 满与空的判据依赖
_size。因为记录了长度，size == 0判空、size == capacity判满都很干净；但如果删掉_size、只留front/rear两个指针，"全满"和"全空"在两个指针上会呈现同一状态，必须引入第三个变量或永远空一格才能区分——这正是保留_size的隐性价值。 - 只守一端。队列被限制为"队尾入、队首出"。若两端都要操作，就需要 array_deque.py 里的双向队列版本：它的
index()方法把取余抽成了独立函数，push_first用(i - 1 + capacity) % capacity实现向左回绕——注意这里先+ capacity再取余，是因为多数语言的负数取余结果仍可能为负，加一次容量就能保证落到合法下标。
另一条岔路是 linkedlist_queue.py：用头、尾两个节点分别充当队首队尾，天然免扩容，但牺牲了数组的缓存局部性，且需要额外维护指针。正文在"队列实现"一节对两者做了完整的优劣对照。想检验自己是否真的理解了取余回绕，exercises.md 里有一道"队尾越过数组末尾怎么办"的手算题——给定front = 3、size = 2的长度 5 环形数组，推演一次入队和一次出队后各变量的取值，正好对应本文的核心公式。
小结与延伸阅读
- 朴素数组队列的痛不在访问，而在假满：
front右移留下的空位无法复用，出队被迫 O(n) 搬移。 - 三个变量撑起全局：
_nums当环形容器，_front指队首，_size记长度并兼作满/空判据。 - 一条公式贯穿所有回绕：
rear = (front + size) % capacity，队尾下标每次现算、不单独维护，天然避免指针失同步。 - 入队、出队各只动一次指针与一个槽位，O(1) 由此而来；
peek直接读_nums[_front]。 - 教学版缺口明确：容量不可变、满时策略因语言而异（抛错 vs 吞掉）、只支持单向操作——分别对应动态扩容、显式错误处理、双向队列三个进阶方向。
延伸阅读：queue.md 章节正文（含链表版实现与典型应用场景）、deque.md 双向队列、stack.md 栈（与队列共享"端点受限"的设计范式）、exercises.md 章节练习题。
【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
