02.02 线性结构：为有限 IM 发送队列选择表示
返回第二卷 · 上一章：离散对象与成本模型 · 学习路线
02.02 线性结构：为有限 IM 发送队列选择表示
DeepTutor 原稿经技术和教学审阅后的章节。所有任务、容量、代码与输出均为静态教学模型；本次没有运行 Go 示例、测试、站点构建或 OpenIM。
本章从哪里开始
01.04、01.05 已介绍切片、结构体和指针；02.01 已说明操作次数、输入规模和渐近界。现在考虑虚构会话 c-a 有三个待处理任务 t-a、t-b、t-c。应先处理谁？容器满了怎样回答？出队后旧任务的正文还会不会留在内存？这些问题既涉及数据结构，也涉及业务约定。
本章只建立顺序执行的有限内存队列。入队成功表示本地容器接纳任务；出队成功表示从容器取出任务。它们都不证明网络发送、服务端受理、持久保存、目标设备接收或用户已读。
| 第一遍 | 第二遍 | 综合 |
|---|---|---|
| 线性次序、切片与链表、栈和队列 | 环形缓冲、不变量、操作成本 | 容量 4 的队列推演和 IM 取舍 |
第一次读一至四节和第八节的起步练习；理解 FIFO 后再读环形缓冲与证明。所有新符号会先以小表解释。
一、线性次序与身份先分开
线性结构把元素安排成一个可逐个前后相接的序列。[t-a, t-b, t-c] 有三个位置：第 0 项、第 1 项、第 2 项。位置回答“当前排在哪里”；任务 ID 回答“它是谁”。取出 t-a 后，t-b 会成为第 0 项，但它仍是 t-b。
同样，任务 ID 不等于消息 ID。一个消息可能对应多台设备的不同计划任务；一次任务失败后重试，也不自动生成新消息。02.01 已用“用户、设备、消息、任务、尝试”区分计量单位，本章继续保留这些身份边界。
我们先约定操作语义：
| 操作 | 输入 | 成功时 | 失败时 |
|---|---|---|---|
| 入队 | 一个任务 | 加到队尾 | 满时拒绝，原队列不变 |
| 出队 | 无 | 取出最早任务 | 空时返回 ok=false，没有伪造的任务 |
| 查看队首 | 无 | 返回最早任务，不删除 | 空时返回 ok=false |
这是一份抽象数据类型（ADT）合同：先规定外部可以做什么，随后才选择切片、链表或环形数组实现。业务规则也要写清“满”的结果；容器不会替产品决定丢弃、等待或重试。
二、连续数组与 Go 切片
数组 [4]Task 的长度固定；切片 []Task 是对底层数组一段范围的描述，包含指向元素区域的信息、长度和容量。切片赋值或子切片可能共享底层数组，append 在容量不足时可能分配新数组并复制元素。01.04 已推演这层共享，本章重点看它对队列生命周期的影响。
tasks := []string{"t-a", "t-b", "t-c"}
first := tasks[0] // 当前第一个任务：t-a。
tasks = tasks[1:] // 当前逻辑次序：t-b、t-c。
_ = firsttasks = tasks[1:] 主要调整切片描述，不搬移 t-b、t-c。这一步的结构操作可视为常数成本，却可能继续引用原底层数组；原来的第 0 槽也可能仍保存旧的字符串引用。若长期使用同一大数组，一路从前部截短，短切片仍可能使大数组留在内存中。
当任务含字符串、切片或指针字段，可先清理已消费槽位：
first := tasks[0]
tasks[0] = ""
tasks = tasks[1:]清零解除原槽对旧任务数据的引用；它不承诺原底层数组立刻被垃圾回收，因为当前切片或其他切片可能仍持有它。若长期只剩少量任务，可在明确阈值时复制剩余部分到新数组，或改用后面的环形队列。
用容量 4 的底层数组做一次纸面追踪：
| 时刻 | 当前切片视图 | 原数组四个槽位 | 还可能持有原数组吗 |
|---|---|---|---|
| 初始 | A、B、C | A、B、C、空 | 是 |
| 截短一次 | B、C | A、B、C、空 | 是，视图仍指向原数组 |
| 清旧槽后截短 | B、C | 空、B、C、空 | 是，但旧 A 的引用已从该槽移除 |
| 复制 B、C 到新数组 | B、C | 原数组仍在，但新视图不引用它 | 还要检查是否有其他旧视图 |
这里有两个不同问题：旧任务对象是否还被槽位引用，以及整个底层数组是否还被某个切片引用。清零针对前者，复制或缩小长期存活的视图针对后者。它们不是“立刻释放若干字节”的保证；真实内存还取决于其他引用与垃圾回收时机。
| 切片操作 | 本章的操作次数模型 | 前提与代价 |
|---|---|---|
已知有效下标的 tasks[i] | O(1) | 随机访问模型；i 必须在 0..len-1 |
| 遍历 n 个任务 | O(n) 次访问 | 若逐项比较可变长度文本，还要计入比较字节 |
尾部 append | 容量足够时 O(1)，扩容一次可 O(n) | 摊还 O(1) 依赖增长策略，不是每次调用的保证 |
前部 tasks=tasks[1:] | 调整切片描述 O(1) | 原数组可能保留；清零与压缩有另外成本 |
| 把剩余元素全部左移一格 | O(n) | 换来紧凑前缀，不是单纯截短 |
这里的 O 记号比较选定的结构操作次数，不等于真实纳秒、吞吐或内存占用。Go 规范没有让课程依赖某个固定的 append 扩容倍率；02.01 的“翻倍数组”只是明确假设下的摊还模型。
三、链表用指针表达相邻关系
单链表的每个节点保存任务和下一个节点的地址：
type node struct {
task Task
next *node
}
type linkedQueue struct {
head *node
tail *node
}三个任务的关系可读成：
head → [t-a | next] → [t-b | next] → [t-c | nil] ← tailhead 指向最早任务，tail 指向最后任务。空队列两者都为 nil；只有一个节点时两者指向同一节点，且该节点的 next 为 nil。从队首出队只需把 head 改为 head.next；若删掉唯一节点，还必须令 tail=nil。已维护 tail 时，尾部入队不用遍历：旧尾指向新节点，再把 tail 改为新节点。
这两个端点操作在“已有头尾指针”的条件下是 O(1)。按 ID 找一条中间任务仍要从头走，最坏 O(n)；若要删除中间节点，通常还需先找到其前驱。链表节点可能分别分配，指针追踪也可能降低局部性。因此不能仅凭“尾插 O(1)”断言链表一定比切片快。
Go 标准库的 container/list 提供双向链表，但它没有为虚构 IM 决定容量、消息身份、出队清理或交付策略。本章先读懂单链的 head、tail、nil，再将库实现作为接口对照。
按 A、B、C 入队，再逐个出队，可以检查头尾是否一直满足约束：
| 操作后 | head | tail | 沿 next 看到的次序 |
|---|---|---|---|
| 新建 | nil | nil | 空 |
| 入 A | A | A | A |
| 入 B | A | B | A→B |
| 入 C | A | C | A→B→C |
| 出 A | B | C | B→C |
| 出 B | C | C | C |
| 出 C | nil | nil | 空 |
如果最后一步只令 head=nil，tail 仍指向已删除的 C。下一次尾插会从错误的旧节点接出新节点，而 head 仍为空；这就是“局部指针操作是 O(1)，却没有维持结构正确”的反例。复杂度分析和不变量检查必须一起做。
四、栈与队列先规定取出顺序
栈按后进先出（LIFO）：依次 Push(A)、Push(B)、Push(C)，第一次 Pop 得到 C。它适合“撤销最近一次本地编辑”的教学模型，但撤销是否允许、怎样影响服务端历史，仍是独立业务规则。
用切片末尾表示栈顶：
func pop(items []string) ([]string, string, bool) {
if len(items) == 0 {
return items, "", false
}
i := len(items) - 1
value := items[i]
items[i] = "" // 清掉已移除槽位的引用。
return items[:i], value, true
}空栈用 ok=false 表示，不把空字符串误当作取出的真实值。一次末尾弹出不需移动剩余元素。若栈元素改为结构体指针或带切片的对象，清理旧槽同样重要。
队列按先进先出（FIFO）：依次 Enqueue(A)、Enqueue(B)、Enqueue(C)，第一次 Dequeue 得到 A，第二次得到 B。它适合描述待处理任务的取出顺序。FIFO 只约束该容器的出队顺序；后续任务可能重试、异步等待或在不同设备上完成，因此不能由 FIFO 推出接收顺序或送达成功。
对短小、临时的队列，切片尾部追加、前部截短已足够。对长期运行且有明确内存上限的顺序队列，可以用固定容量环形缓冲复用消费过的槽位。它的代价是必须规定满时如何处理。
把行为与实现分开还能发现需求冲突。例如一个“撤销最近一次编辑”的栈，即使内部也使用切片，取出顺序仍是 C、B、A；一个待处理任务队列是 A、B、C。若实际需求是“先处理最高优先级”，那既不是普通栈也不是普通 FIFO 队列，应到 02.07 再讨论堆与优先调度。不要因为三者都能用切片存数据，就认为它们的业务语义相同。
五、环形队列的三个状态量
设容量 C=4，物理槽下标是 0,1,2,3。队列维护：
head：下一次成功出队所读的槽；空时只是下次可能入队的位置。count：当前有效任务数，必须满足0 ≤ count ≤ C。tail：下一次入队要写的槽，由(head + count) % C计算，不另存一份可漂移状态。
空是 count==0，满是 count==C。不能只用 head==tail 判断，因为空和绕满一圈后都可能相等。C 必须大于 0，否则取模没有定义。
按“先 A、B、C；出队 A、B；再入队 D、E、F”逐步推导：
| 操作后 | head | count | tail 下一写槽 | 逻辑次序 | 物理有效槽 |
|---|---|---|---|---|---|
| 新建 | 0 | 0 | 0 | 空 | 无 |
| 入 A | 0 | 1 | 1 | A | 0:A |
| 入 B | 0 | 2 | 2 | A,B | 0:A 1:B |
| 入 C | 0 | 3 | 3 | A,B,C | 0:A 1:B 2:C |
| 出 A | 1 | 2 | 3 | B,C | 1:B 2:C |
| 出 B | 2 | 1 | 3 | C | 2:C |
| 入 D | 2 | 2 | 0 | C,D | 2:C 3:D |
| 入 E | 2 | 3 | 1 | C,D,E | 2:C 3:D 0:E |
| 入 F | 2 | 4 | 2 | C,D,E,F | 2:C 3:D 0:E 1:F |
最后 head==tail==2，但 count==4，所以是满。若再请求入 G，本章选择返回失败并保持上述四项不变，不覆盖 C。随后成功出队 C、D、E、F，head 依次为 3、0、1、2，count 依次为 3、2、1、0。每次出队把旧槽清零，最后空队列的 head==tail==2。
要手工核对某一行，先计算“队首之后第 j 个任务”的物理下标 (head+j)%C，其中 0≤j<count。例如满时 head=2,count=4：j=0,1,2,3 依次访问槽 2、3、0、1，正好得到 C、D、E、F。此公式只在 j 是当前有效逻辑位置时可用；不能把槽 0 永久称为第一条消息。
这张表以逻辑有效槽标示数据。被清零的物理槽不属于队列，即使内存中曾放过别的任务，也不能凭旧内容把它读成有效任务。
六、用 Go 写一个顺序、固定容量的队列
下面是独立的完整程序。Task.ID 仅是本地计划任务身份；RingQueue 没有锁、网络或持久化能力。返回 (Task,bool) 是为了区分空队列与一个字段恰好为零值的合法任务。
package main
import (
"errors"
"fmt"
)
type Task struct {
ID string
Body string
}
type RingQueue struct {
slots []Task
head int
count int
}
func NewRingQueue(capacity int) (*RingQueue, error) {
if capacity <= 0 {
return nil, errors.New("队列容量必须大于零")
}
return &RingQueue{slots: make([]Task, capacity)}, nil
}
func (q *RingQueue) Len() int {
if q == nil {
return 0
}
return q.count
}
func (q *RingQueue) Cap() int {
if q == nil {
return 0
}
return len(q.slots)
}
func (q *RingQueue) Enqueue(task Task) bool {
if q == nil || q.count == len(q.slots) {
return false
}
tail := (q.head + q.count) % len(q.slots)
q.slots[tail] = task
q.count++
return true
}
func (q *RingQueue) Dequeue() (Task, bool) {
if q == nil || q.count == 0 {
return Task{}, false
}
task := q.slots[q.head]
q.slots[q.head] = Task{} // 移除槽位里的字符串引用。
q.head = (q.head + 1) % len(q.slots)
q.count--
return task, true
}
func main() {
q, err := NewRingQueue(4)
if err != nil {
fmt.Println(err)
return
}
for _, id := range []string{"A", "B", "C"} {
if !q.Enqueue(Task{ID: id}) {
fmt.Println("初始入队失败", id)
return
}
}
for i := 0; i < 2; i++ {
task, ok := q.Dequeue()
if !ok {
fmt.Println("预期取出失败")
return
}
fmt.Println("取出", task.ID)
}
for _, id := range []string{"D", "E", "F"} {
if !q.Enqueue(Task{ID: id}) {
fmt.Println("回绕入队失败", id)
return
}
}
fmt.Println("满时入 G", q.Enqueue(Task{ID: "G"}))
fmt.Println("当前长度", q.Len(), "容量", q.Cap())
}按状态表预期先取出 A、B；入 D、E、F 后为满，入 G 返回 false，长度为 4、容量为 4。这是规则推导，不是运行输出。Enqueue 满时在写槽之前返回，所以旧任务不会被覆盖；Dequeue 先保存旧 head 的任务、清槽，再前移并减少计数。
这个结构只按顺序使用。多个 goroutine 同时操作会引入共享状态问题，不能因方法各为 O(1) 就称它并发安全。实际 IM 的任务提交、发送确认和故障恢复也需要另外设计。
七、第二遍：不变量、成本与容量决策
不变量是在每次公开操作完成后仍成立的性质。本队列有四条：C>0；0≤head<C；0≤count≤C；从 head 起跨越 count 个槽依次是逻辑任务。构造时 head=count=0，成立。
入队在 count<C 时写入 tail=(head+count)%C，再令 count 加一；写入前该槽不在有效范围中，写入后恰好成为新队尾。满时返回且状态不变。出队在 count>0 时读取旧 head，清零，令 head=(head+1)%C、count 减一；剩余任务的相对次序不变。空时返回且状态不变。因而每次操作都保持约束。
在容量已经分配、Task 字段大小固定的模型中，单次入队和出队只做固定次数的索引、读写与整数更新，所以结构操作为 O(1)。这不包括：构造 C 个槽需要 O(C) 初始化；从消息生成任务可能随设备数增长；复制大正文、排队等待、网络发送、重试和落盘都另算成本。O(1) 不等于“响应一定很快”。
| 结构 | 队首出队 | 队尾入队 | 第 i 项访问 | 内存与容量条件 |
|---|---|---|---|---|
| 切片前移视图 | 调整描述 O(1) | 容量足够时 O(1)，扩容一次可 O(n) | O(1) | 可能保留大底层数组，需清槽或压缩 |
| 有头尾的单链 | O(1) | 已维护尾指针时 O(1) | O(n) | 节点分配、指针与局部性成本 |
| 固定环形缓冲 | O(1) | 未满时 O(1) | O(1) 需按逻辑下标换算 | 固定 C，满时必须有明确策略 |
满队列策略是业务决定。 可拒绝新任务、等待消费者、扩容、转存其他介质，或在允许丢弃的业务中明确丢弃。每种选择改变延迟、内存和失败语义。本章只实现“拒绝且不改变队列”；调用方必须处理 false，不能把它当成功，也不能悄悄丢弃尚未处理的任务。队列长度只描述当前本地积压，不是“未送达用户数”。
设容量为 4，一瞬间有 A、B、C、D、E 五个任务到达，消费者尚未出队。第五个 E 到来时，单靠数据结构只知道“没有空槽”。上层至少要选一种明确合同：
| 上层选择 | E 的结果 | 额外需要回答的问题 |
|---|---|---|
| 拒绝入队 | Enqueue(E)==false | 调用者怎样反馈与重试？是否已有可靠的任务记录？ |
| 等待空槽 | E 暂不入队 | 最长等多久？等待是否阻塞请求？取消如何处理？ |
| 扩容到更大数组 | E 进入新容量 | 内存上限是多少？迁移期间如何维护次序？ |
| 写入其他介质 | E 转交另一处理路径 | 哪个介质是权威？何时确认？失败怎样恢复？ |
本章只实现第一行。若某个产品承诺“消息绝不因队列满而丢失”，仅返回 false 还不够；调用者必须在外层有相应处理。相反，强行覆盖最旧任务会改变 FIFO 的任务集合，也可能丢掉尚未执行的工作。队列方法的返回值必须与业务层的承诺接上。
八、分层练习与 IM 取舍
选择结构时先写出主要操作与容量条件：聊天历史常需要按位置读取和连续扫描，切片可作起步表示；本地“撤销最近一次编辑”符合栈的 LIFO；有限待处理任务要求 FIFO、容量明确和出队清理，可比较切片、链表与环形缓冲。按 ID 快速查找或删除另需索引；结构的当前下标不能替代稳定消息 ID。
1. `tasks[0]` 是任务身份吗？
不是，只是当前第一个位置。出队后原 tasks[1] 会成为新队首，ID 不变。
2. 一条消息面向两台设备形成几个教学任务？
在“每条消息每台设备一任务”的明确模型中为两个；消息仍只有一条。
3. `tasks=tasks[1:]` 会搬移所有剩余元素吗？
不会，它主要改变切片描述；原底层数组可能继续被引用。
4. 为什么出队前清掉旧槽？
Task 的字符串等引用不应在逻辑删除后仍由存活的数组槽长期持有。
5. `append` 的每一次调用都是 O(1) 吗？
不是。容量不足的一次可能分配并复制 O(n) 个元素；摊还分析需要增长策略前提。
6. 有头尾指针的单链，删除唯一节点后怎样更新？
同时令 head=nil、tail=nil；只清其中一个会留下不一致状态。
7. 只知道一个消息 ID，单链表能 O(1) 删除对应任务吗？
通常不能。先按 ID 找节点或前驱仍需遍历，除非另有索引与相应指针。
8. 栈依次压入 A、B、C，第一次弹出谁？
C；这是后进先出。它不自动表示服务端撤回了 C。
9. 队列依次入 A、B、C，第一次出队谁？
A；这是先进先出，只规定此容器的取出顺序。
10. 容量 4、`head=2`、`count=3`，`tail` 是几？
(2+3)%4=1，下一次写下标 1。
11. `head==tail` 能单独判断空吗？
不能；count=0 为空，count=C 为满，两者都可能令下标相等。
12. 为什么构造时拒绝 `capacity=0`？
所有取模与访问都要求正容量，%0 无定义。
13. 容量 4 的推演中，出 B 后逻辑队列是什么？
只有 C，head=2,count=1,tail=3。
14. 再入 D、E、F 后逻辑队列是什么？
C、D、E、F；head=2,count=4,tail=2，已满。
15. 已满时入 G，本章结果是什么？
返回 false，C、D、E、F 和三个状态量均保持不变。
16. 空队列出队返回零值任务，如何区分真实结果？
同时返回 ok=false；不能只看 Task{} 的字段。
17. 出队完成是否等于任务执行成功？
不等于。它只从本地队列移走任务；后续发送、确认、重试另有状态。
18. 固定环形队列入队 O(1) 能说明发送时延 O(1) 吗？
不能。排队等待、消息大小、网络、设备数量和重试都在结构操作以外。
19. 为什么链表不一定比切片快？
节点分配、指针追踪与局部性有成本；只比较大 O 不能得到真实耗时结论。
20. 阅读公开 IM 项目队列时先问什么？
确认任务身份、容量、满载处理、出队清理、确认点和恢复条件；不能仅看容器名称推断可靠性。
来源与下一步
- Algorithms, 4th Edition：栈与队列用于核对抽象操作和数组、链表实现的取舍；教材中的 Java 语法没有移植为 Go 规则。
- MIT 6.006 课程笔记目录用于核对数组、动态数组与成本模型。
- Go 切片内部说明与container/list用于核对 Go 表示边界。
下一章02.03 搜索与循环不变量从顺序结构进入查找：先线性扫描，再在明确排序与区间约定后学习二分。本章没有审计 OpenIM 固定版本的具体队列；后续源码阅读须分别核对容量、状态和确认语义。