第 10 章 基本数据结构

本章对应原书 Part III 导言与第 10 章。它讲的东西看起来很朴素：栈、队列、链表、有根树，以及在没有指针的环境里怎样用数组"造出"对象和指针。但交易系统里最常见的几个底层部件——行情环形缓冲区、价位上的委托队列、撤单索引、对象池——几乎都是这几样东西的直接组合。

学习目标

读完本章，你应当能够：

1. 说清"动态集合"的概念，以及查询操作与修改操作的区别，尤其是 DELETE 接收指针而不是关键字这一约定的工程含义。
2. 用数组实现栈和循环队列，并解释循环队列为什么 \(n\) 个槽最多只能放 \(n-1\) 个元素。
3. 写出双向链表的搜索、插入、删除，理解哨兵（sentinel）如何消掉边界判断。
4. 用多数组表示和自由表（free list）在 \(O(1)\) 时间内分配和回收同构对象，并把它对应到交易系统的内存池。
5. 掌握二叉树与"左孩子右兄弟"两种有根树表示。
6. 用环形缓冲区和单调双端队列实现滚动波动率、滚动最高价等流式指标，用"散列表 + 双向链表"实现价位队列的 \(O(1)\) 撤单。

读前导读

这一章在解决什么问题。 "数据结构"听起来很技术，其实就是数据怎么摆放。同样一批订单，摆法不同，"找到某一笔""删掉某一笔""取出最早的一笔"所花的时间可以差成千上万倍。你在 Excel 里也有体会：一张按时间排好的成交明细表，取"最新一笔"很快（看最后一行），但要从中间删掉一行再让下面的行全部上移，表一大就很慢。

本章介绍四种最基础的摆法，每种都可以对应到交易所或交易系统里的一个具体场景：

• 栈（后进先出）：像一摞盘子，只能从顶上放、从顶上拿。交易系统里撤销最近一步操作、解析因子公式时用到。
• 队列（先进先出）：像柜台前排队。同一价位上的委托按"时间优先"排队成交，就是队列。
• 链表：每个元素手里拉着前后邻居的"手"，不要求在内存里挨着放。好处是从中间抽掉一个元素只需让它前后两人重新拉手，不必挪动其他人——这正是撤单需要的。
• 有根树：像公司组织架构或 FoF 的"母基金 → 子基金 → 底层资产"层级。

本章还有一个贯穿全书的概念叫指针：可以把它理解为"储物柜编号"或"仓位在系统里的内部 ID"——拿到编号就能直接走到那个柜子前，不必从头一个个找。很多操作快不快，取决于你手里有没有这个编号。

需要先想起来的数学。 本章几乎没有推导，只需要三样东西：

• 大 O 记号。 \(O(1)\) 表示"不管数据多大，耗时都是常数"，比如按柜子编号直接开柜；\(O(n)\) 表示"耗时与数据量成正比"，比如从头到尾翻一遍成交明细找某一笔。\(\Theta(n)\) 表示"恰好是这个量级，不多也不少"。见本册第 03 章和 第 00 册第 07 章 概率中的分析工具 中的"大 O 小 o"。
• 取模运算 \(a \bmod n\)（代码里写 a % n）。 就是"除以 \(n\) 的余数"。\(7\bmod5=2\)，\(10\bmod5=0\)。像钟表：12 点之后又回到 1 点。循环队列和环形缓冲区的"写到尽头就绕回开头"全靠它。
• 方差的另一种写法。 \(\text{Var}(X)=E[X^2]-(E[X])^2\)；对样本则是 \(s^2=\frac{\sum x_i^2-n\bar x^2}{n-1}\)。所以只要随时记着"和"与"平方和"，任何时刻都能马上算出方差，这是 10.6.1 节滚动波动率的依据。见 第 00 册第 07 章 概率中的分析工具。
• 摊还（平均到每步）的意思。 某一步可能很慢，但一长串操作的总耗时除以步数是常数，就说"摊还 \(O(1)\)"。类比：设备一次性大额支出按年折旧，每年分摊的费用是平稳的。详细见本册第 17 章。

怎么读这一章。 10.1 节的操作表和"DELETE 接收指针"那段是后面四章的共同语言，必读。10.2、10.3 节是核心，建议拿纸画一画指针怎么变。10.4 节读懂"自由表就是对象池"即可，单数组表示可以略读。10.5 节只需知道两种树的表示。10.6 节量化实战是本章最有价值的部分，订单簿价位队列那段建议逐行读代码。

10.1 动态集合：本部分的共同语言

数学里的集合是不变的；算法里的集合会随时间增长、收缩或变化，称为动态集合（dynamic set）。原书第 10–14 章讨论的都是怎样在计算机上表示有限动态集合，并高效支持其上的操作。

元素的表示。 每个元素是一个对象，通过指向它的指针可以读写它的属性。很多动态集合假定对象有一个用来标识的关键字（key）；对象还可以带卫星数据（satellite data）——集合实现本身不看它，只是随对象一起搬动。比如一个订单对象，关键字是订单 ID，价格、数量、账户等都是卫星数据。如果关键字来自全序集（totally ordered set）（实数、按字典序的字符串），就可以谈论"最小元素""下一个更大的元素"。

只支持插入、删除、成员测试的动态集合叫字典（dictionary）。

白话解释：交易日内的"当前挂单集合"就是一个典型的动态集合：每秒都有新单进来（插入）、成交或撤单离开（删除）。"关键字"是你用来认出一笔订单的东西（订单号），"卫星数据"是跟着订单走、但集合本身不关心的信息（价格、数量、账户）。"全序"的意思是任意两个关键字都能比大小，例如价格；有了全序，才能问"最低卖价是多少""比 10.05 高一档的价位是哪个"。"字典"只关心"有没有这笔订单"，不关心顺序，就像按订单号查询的柜台系统。

典型操作分为**查询（queries）和修改操作（modifying operations）**两类：

有一点初学者常忽略：DELETE 的参数是指针，不是关键字值。 如果手里只有关键字，就得先 SEARCH。这个约定后面会反复出现——链表删除之所以能 \(O(1)\)、撮合引擎撤单之所以能 \(O(1)\)，都依赖"已经拿到了指针"。

金融直觉：想象托管行的保管箱。客户说"把我那份债券凭证取出来"，如果只报姓名（关键字），柜员得翻登记簿找到箱号（SEARCH）；如果客户直接给箱号（指针），柜员走过去开箱就行。DELETE 规定"给箱号"，是把"找"和"删"拆成两步，让删除本身的成本单独可控。撮合引擎收到撤单请求时只有订单号，所以它会额外维护一张"订单号 → 箱号"的对照表（10.6.2 节用散列表实现），先 \(O(1)\) 查到箱号，再 \(O(1)\) 删除。

对 \(n\) 个关键字，先调一次 MINIMUM 再调 \(n-1\) 次 SUCCESSOR，就能按序枚举全部元素。时间一般以集合大小 \(n\) 衡量。

本部分路线图。 第 10 章：栈、队列、链表、有根树；第 11 章：散列表，期望 \(O(1)\) 的字典；第 12 章：二叉搜索树，所有操作 \(O(h)\)；第 13 章：红黑树，最坏 \(O(\lg n)\)；第 14 章：在红黑树上"扩张"出顺序统计和区间查询。本册把第 12、13 章合为一章。第 6 章的堆也是重要的数据结构（见本册第 06 章）。

10.2 栈和队列

栈和队列都是"删除哪个元素事先确定"的动态集合：

• **栈（stack）**删除最近插入的元素，后进先出（LIFO, last-in first-out）；
• **队列（queue）**删除在集合中停留最久的元素，先进先出（FIFO, first-in first-out）。

10.2.1 栈的数组实现

用数组 \(S[1..n]\) 实现最多 \(n\) 个元素的栈，属性 \(S.top\) 指向栈顶元素的下标；栈由 \(S[1..S.top]\) 构成，\(S.top=0\) 表示空栈。插入叫 PUSH，删除叫 POP。对空栈 POP 叫下溢（underflow），超过容量叫上溢（overflow）。

def STACK_EMPTY(S):  return S.top == 0
def PUSH(S, x):
    S.top += 1; S[S.top] = x
def POP(S):
    if STACK_EMPTY(S): raise Exception("underflow")
    S.top -= 1
    return S[S.top + 1]      # 元素仍留在数组里，但已不属于栈

三个操作都是 \(O(1)\)。原书图 10.1：栈有 4 个元素、栈顶为 9；PUSH 17、PUSH 3 后 \(S.top=6\)；POP 返回 3，\(S.top=5\)，3 仍在数组第 6 格中，但已不在栈里。

10.2.2 队列的循环数组实现

队列的插入叫 ENQUEUE，删除叫 DEQUEUE。用 \(Q[1..n]\) 实现：\(Q.head\) 指向队头，\(Q.tail\) 指向下一个新元素要放的位置；元素占据 \(Q.head, Q.head+1,\dots,Q.tail-1\)，并且环绕（wrap around）——位置 1 紧接在位置 \(n\) 后面。

• \(Q.head = Q.tail\) 时队列为空，初始 \(Q.head=Q.tail=1\)；
• \(Q.head = Q.tail+1\)（或 \(Q.head=1\) 且 \(Q.tail=n\)）时队列为满。

def ENQUEUE(Q, x):
    Q[Q.tail] = x
    Q.tail = 1 if Q.tail == Q.length else Q.tail + 1
def DEQUEUE(Q):
    x = Q[Q.head]
    Q.head = 1 if Q.head == Q.length else Q.head + 1
    return x

推导拆解：用 \(n=4\) 个槽走一遍。初始 head=tail=1，空。依次入队 a、b、c：a 放 1 号，b 放 2 号，c 放 3 号，tail 依次变成 2、3、4。此时 head=1、tail=4，满足"\(head=1\) 且 \(tail=n\)"，判定为满，只放了 3 个。假如允许再放 d 到 4 号，tail 会绕回 1，变成 head=tail=1——和"空"的状态一模一样，程序就分不清了。出队 a 后 head=2，再入队 d 放到 4 号，tail 绕回 1；这时 head=2=tail+1，又是满。"绕回"那一步就是 \(tail=(tail\bmod n)+1\)，代码里写成 if 判断。

均为 \(O(1)\)。为什么容量只有 \(n-1\)？ 因为只靠 head 和 tail 两个指针，"空"与"满"都可能表现为指针相等；故意留一个空位，就能用 \(head=tail\) 表示空、\(head=tail+1\) 表示满。工程上另一种做法是额外维护一个元素计数（下文的环形缓冲区就是这样）。

原书图 10.2：\(Q[1..12]\) 中 5 个元素位于 \(Q[7..11]\)；依次入队 17、3、5 后 tail 环绕到 3；出队返回 15，head 变为 8。

习题中的两个变形值得记住。 一是双端队列（deque, double-ended queue），两端都能 \(O(1)\) 插入和删除（习题 10.1-5），它是后面"单调队列"的基础；二是用两个栈实现队列（习题 10.1-6），单次操作最坏 \(O(n)\)，但摊还 \(O(1)\)，这是摊还分析（本册第 17 章）的入门例子。

10.3 链表

**链表（linked list）**中对象按线性顺序排列，但顺序由对象里的指针决定，而不是数组下标。

双向链表（doubly linked list） \(L\) 的每个元素有 key、next、prev 三个属性。\(x.prev=\text{NIL}\) 表示 \(x\) 是表头，\(x.next=\text{NIL}\) 表示 \(x\) 是表尾，\(L.head\) 指向第一个元素。其他变体：**单向链表（singly linked）**省略 prev；**有序表（sorted）**表头最小、表尾最大；**循环链表（circular list）**首尾相接。

10.3.1 搜索、插入、删除

def LIST_SEARCH(L, k):           # 最坏 Θ(n)
    x = L.head
    while x is not NIL and x.key != k:
        x = x.next
    return x

def LIST_INSERT(L, x):           # 插到表头，O(1)
    x.next = L.head
    if L.head is not NIL:
        L.head.prev = x
    L.head = x
    x.prev = NIL

def LIST_DELETE(L, x):           # 给定指针 x，把它"剪"出去，O(1)
    if x.prev is not NIL: x.prev.next = x.next
    else:                 L.head = x.next
    if x.next is not NIL: x.next.prev = x.prev

原书图 10.3：集合 \(\{1,4,9,16\}\) 存为链表 9→16→4→1；LIST-SEARCH(L,4) 返回第三个元素，LIST-SEARCH(L,7) 返回 NIL；插入 25 后它成为新表头。

要点：LIST-DELETE 本身 \(O(1)\)，但若只知道关键字，先搜索就要 \(\Theta(n)\)。而且删除要 \(O(1)\) 必须是双向链表——单向链表要先找到前驱（习题 10.2-1）。

白话解释：数组像电影院的一排座位，座位号连续；要把中间某人请走并保持"没有空座"，他右边所有人都得挪一格，\(\Theta(n)\)。链表像一队手拉手的人，站在哪里无所谓，顺序由"谁拉着谁"决定。请走中间的 B（A—B—C）时，只需让 A 的右手改拉 C、C 的左手改拉 A，其他人不动，\(O(1)\)。LIST-DELETE 的两个 if 就是这两次"换手"，外加处理 B 恰好在队首或队尾的特殊情况。 单向链表只有"右手"：站在 B 的位置，你不知道左边是谁，必须从队首重新数到 A，才能让 A 改拉 C，所以删除退化成 \(\Theta(n)\)。这就是价位委托队列要用双向链表的原因。

10.3.2 哨兵

忽略边界条件时，删除只需两行：x.prev.next = x.next; x.next.prev = x.prev。哨兵（sentinel）就是为了让这两行永远成立而设的哑对象 \(L.nil\)：它代表 NIL，但拥有普通对象的全部属性。链表于是变成带哨兵的双向循环链表：\(L.nil.next\) 指向表头，\(L.nil.prev\) 指向表尾，表头的 prev、表尾的 next 都指向 \(L.nil\)；空表时 \(L.nil.next = L.nil.prev = L.nil\)。

def LIST_SEARCH_(L, k):
    x = L.nil.next
    while x is not L.nil and x.key != k:
        x = x.next
    return x
def LIST_INSERT_(L, x):
    x.next = L.nil.next; L.nil.next.prev = x
    L.nil.next = x;      x.prev = L.nil
def LIST_DELETE_(L, x):
    x.prev.next = x.next; x.next.prev = x.prev

哨兵很少改变渐近复杂度，它的价值在于代码更短、分支更少。在热点循环里少一个分支，常数因子就会改善（习题 10.2-4 把待找的 \(k\) 放进哨兵的 key，还能把 x is not L.nil 的测试也省掉）。代价是每个链表多一个对象；若有大量很短的链表，哨兵的存储开销就不可忽略。原书的态度是：只在确实简化代码时才用。

白话解释：哨兵是一个"不代表任何真实订单的占位人"，固定站在队伍的首尾交界处，整队人围成一个圈。这样一来，每个真实订单左右两边永远有人（最坏也是哨兵），删除时就不必问"他是不是队首？是不是队尾？"，两次换手永远合法。空队列就是哨兵自己左手拉右手。对照前后两版 LIST_DELETE：没有哨兵时 4 行加 2 个 if，有哨兵时 1 行。撮合引擎每秒处理几十万次撤单，少掉的分支判断是真实的延迟节省。

10.4 用数组实现指针和对象

在没有显式指针类型的语言里，或者在你不想让内存分配器介入的低延迟系统里，可以用数组和下标合成对象与指针。

多数组表示（multiple-array representation）。 对一组同属性的对象，每个属性用一个数组：key[x]、next[x]、prev[x] 合起来表示一个对象，"指针" \(x\) 就是公共下标。NIL 用不可能是合法下标的整数（如 0 或 \(-1\)）表示。这就是今天说的**结构数组（struct of arrays）**列式布局：同一属性连续存放，对 CPU 缓存和向量化友好。因子计算框架按列存储数据，是同一个思想。

单数组表示（single-array representation）。 所有对象放在一个数组 \(A\) 里，对象占连续子数组 \(A[j..k]\)，指针就是首下标 \(j\)，属性通过"指针 + 偏移量（offset）"访问。原书图 10.6 中 key、next、prev 的偏移分别是 0、1、2，读 \(i.prev\) 就是读 \(A[i+2]\)。它允许不同长度的对象共存，但管理**异构（heterogeneous）对象比同构（homogeneous）**对象难。这其实就是 C 语言结构体在内存里的样子。

对象的分配与释放。 多数组长度为 \(m\)、集合当前有 \(n\) 个元素时，其余 \(m-n\) 个对象空闲。把空闲对象串成单向链表，称为自由表（free list），表头存在全局变量 free 中：

def ALLOCATE_OBJECT():
    if free is NIL: raise Exception("out of space")
    x = free
    free = x.next        # 相当于 POP
    return x

def FREE_OBJECT(x):
    x.next = free        # 相当于 PUSH
    free = x

自由表本质上是一个栈：下一次分配到的是最近释放的那个对象（它很可能还在缓存里，这是附带的好处）。两个操作都是 \(O(1)\)。一个自由表可以服务多个链表（原书图 10.8）；每个对象要么在某个链表中，要么在自由表中，不会同时属于两者。

白话解释：多数组表示可以想成一张行情表的"列式存储"：第 \(x\) 行的订单，它的数量在 qty 列第 \(x\) 格，它后面那笔订单的行号在 next 列第 \(x\) 格。所谓"指针"，就是行号。自由表则像前台的一串空柜钥匙：来了新订单，从钥匙串最上面取一把（ALLOCATE，即 POP）；订单撤销或成交完，把钥匙挂回最上面（FREE，即 PUSH）。钥匙串用每个空柜的 next 格串起来，所以不需要额外的存储。 不变式"每个对象要么在某个链表中、要么在自由表中"相当于会计里的"资产 = 已使用 + 闲置"，10.6.2 节压力测试的最后一行就是在做这种轧账。

这套机制在交易系统里叫对象池（object pool）或内存池：开盘前一次性预分配好全部订单对象，盘中只在自由表上 PUSH/POP，不调用系统分配器，也就没有分配延迟的抖动，在有垃圾回收的语言里还能避免 GC 停顿。

10.5 有根树的表示

把链表的思路推广：每个树结点是一个对象，带 key，其余属性是指向其他结点的指针。

• 二叉树：属性 p、left、right 分别指向父结点、左孩子、右孩子；\(x.p=\text{NIL}\) 表示根，\(T.root\) 指向根，\(T.root=\text{NIL}\) 表示空树。
• 孩子数有界的树：最多 \(k\) 个孩子时可用 \(child_1,\dots,child_k\)；但孩子数无界时无法预先确定属性个数，\(k\) 很大而多数结点孩子很少时又浪费空间。
• 左孩子右兄弟表示（left-child, right-sibling representation）：每个结点只有三个指针——父指针 \(p\)、指向最左孩子的 left-child、指向右侧紧邻兄弟的 right-sibling。任意 \(n\) 结点有根树只需 \(O(n)\) 空间。

白话解释：用公司组织架构理解"左孩子右兄弟"。总经理下面有 8 个部门经理，财务部下面只有 2 人，交易部下面有 30 人——如果给每人预留"下属 1 号 … 下属 30 号"的格子，绝大多数格子是空的。左孩子右兄弟的做法是：每个人只记三件事——上级是谁、自己的第一个下属是谁、自己右边紧挨着的同级同事是谁。要列出交易部全体员工，就先找到交易部经理的第一个下属，再沿着"右边同事"一路走下去。每人固定 3 个格子，总空间与人数成正比。 术语："有根树"指有一个最顶层结点（根）的树；"父结点""孩子"就是上下级；"叶子"是没有下属的结点。

其他表示依应用而定：堆用一个数组表示完全二叉树；不相交集合森林（原书第 21 章）只需要向根走，所以只存父指针。

原书第 10 章的思考题 10-1 要求给出四种链表（无序/有序 × 单向/双向）上七种操作的最坏时间。结论是：有序表 INSERT 需 \(\Theta(n)\) 找位置；单向表 DELETE 和 PREDECESSOR 需 \(\Theta(n)\) 找前驱；无序表 MIN/MAX/SUCCESSOR 需 \(\Theta(n)\) 扫描。没有一种链表能让所有操作都快——这正是后面几章要解决的问题。思考题 10-3 给出一个有意思的随机算法：紧凑存放的有序链表上，先做 \(t\) 次随机跳跃再顺序走，期望时间 \(O(t+n/t)\)，取 \(t=\sqrt n\) 得 \(O(\sqrt n)\)。

10.6 量化实战

10.6.1 流式指标：环形缓冲区与单调队列

实时策略面对的是一条源源不断的 tick 或 K 线流，许多指标只依赖最近 \(w\) 个观测：滚动均值、滚动波动率、\(w\) 日最高价（突破信号）、回撤。两种结构最常用：

**环形缓冲区（ring buffer）**就是 10.2 节的循环队列：固定容量、新数据覆盖最旧数据、写指针环绕。在它上面增量维护窗口的和与平方和，滚动方差每步 \(O(1)\)。

**单调双端队列（monotonic deque）**用来求滑动窗口最大值。队列里存下标，保持对应的值从队头到队尾单调递减：新值到来时，先从队尾弹出所有不大于它的元素（它们在新值离开窗口之前不可能再成为最大值），再把新值放到队尾；队头若已滑出窗口就从队头弹出。队头始终是窗口最大值。每个下标最多进队一次、出队一次，所以处理 \(N\) 个数据点总共 \(O(N)\)，每步摊还 \(O(1)\)，与窗口长度无关；而每步重新扫描窗口是 \(O(w)\)。

推导拆解：取窗口 \(w=3\)，价格依次为 5、3、4、6、2。 第 1 天价 5：队列 [5]，最大 5。 第 2 天价 3：3 不大于队尾 5，直接排队尾，队列 [5, 3]，最大 5。 第 3 天价 4：从队尾弹出不大于 4 的 3（3 比 4 早离开窗口又比 4 小，以后不可能当最大值），队列 [5, 4]，最大 5。 第 4 天价 6：从队尾弹出 4，再弹出 5，队列 [6]；最大 6。 第 5 天价 2：排到队尾，队列 [6, 2]；6 是第 4 天的，仍在窗口（第 3–5 天）内，最大 6。 队列里存的是"仍有可能成为窗口最大值的候选人"，按价格从高到低排，队头就是答案。为什么总共 \(O(N)\)：虽然某一天可能一次弹出很多元素（第 4 天弹了两个），但每个元素一生只进队一次、最多出队一次，\(N\) 天合计进出至多 \(2N\) 次。这就是"摊还 \(O(1)\)"。 环形缓冲区那边的依据是 \(s^2=\frac{\sum x^2-n\bar x^2}{n-1}\)：新数据进来时把它加进"和"与"平方和"，被覆盖的旧数据从两者中减掉，任何时刻都能直接算出方差。

import numpy as np
from collections import deque

class RingBuffer:
    """固定容量的循环数组：保存最近 n 个 tick，O(1) 追加，并增量维护均值与方差。"""
    def __init__(self, n):
        self.buf = np.empty(n)
        self.n, self.head, self.size = n, 0, 0     # head 指向下一个写入位置
        self.s1 = 0.0; self.s2 = 0.0               # 窗口内的和、平方和
    def push(self, x):
        if self.size == self.n:                     # 已满：覆盖最旧元素
            old = self.buf[self.head]
            self.s1 -= old; self.s2 -= old * old
        else:
            self.size += 1
        self.buf[self.head] = x
        self.s1 += x; self.s2 += x * x
        self.head = (self.head + 1) % self.n        # 环绕
    def mean(self): return self.s1 / self.size
    def var(self):                                  # 样本方差
        m = self.mean()
        return (self.s2 - self.size * m * m) / (self.size - 1)

def rolling_max_deque(x, w):
    """单调双端队列：队列中下标对应的值单调递减，队头即窗口最大值。每个下标进出队各一次，摊还 O(1)。"""
    dq, out = deque(), np.empty(len(x))
    for t, v in enumerate(x):
        while dq and x[dq[-1]] <= v:   # 从队尾弹出不可能再成为最大值的元素
            dq.pop()
        dq.append(t)
        if dq[0] <= t - w:             # 队头已滑出窗口
            dq.popleft()
        out[t] = x[dq[0]]
    return out

rng = np.random.default_rng(7)
ret = rng.normal(0, 0.01, 2000)
price = 100 * np.exp(np.cumsum(ret))

rb, w = RingBuffer(250), 250
rv = []
for r in ret:
    rb.push(r)
    rv.append(np.sqrt(rb.var()) if rb.size == w else np.nan)
rv = np.array(rv)
ref = np.array([ret[t-w+1:t+1].std(ddof=1) if t >= w-1 else np.nan for t in range(len(ret))])
print("环形缓冲区滚动波动率 与 直接计算 的最大误差:", np.nanmax(np.abs(rv - ref)))

hh = rolling_max_deque(price, 60)
ref_hh = np.array([price[max(0, t-59):t+1].max() for t in range(len(price))])
print("单调队列滚动最高价 与 暴力法 一致:", np.allclose(hh, ref_hh))
breakout = price >= hh            # 创 60 日新高
dd = price / rolling_max_deque(price, len(price)) - 1   # 窗口=全样本 → 回撤序列
print("创 60 日新高的天数:", int(breakout[59:].sum()), " 最大回撤: %.2f%%" % (100 * dd.min()))

运行输出：

环形缓冲区滚动波动率 与 直接计算 的最大误差: 8.673617379884035e-18
单调队列滚动最高价 与 暴力法 一致: True
创 60 日新高的天数: 109  最大回撤: -62.95%

两点工程提醒。第一，用"平方和减均值平方"算方差，在长时间流式运行、且数据均值远大于标准差（比如直接对价格而不是收益率算）时会出现严重的相消误差；对价格水平做滚动方差，应改用 Welford 增量公式，或定期从缓冲区全量重算以校正漂移。第二，上面把窗口取成整个样本时，滚动最大值就是历史最高点，price / 历史最高 - 1 就是回撤序列，这正是回测报告里最大回撤的标准算法。

10.6.2 价位委托队列：哨兵双向链表 + 散列表 + 自由表

交易所撮合遵循"价格优先、时间优先"。同一价位上的委托按到达先后排队，是一个 FIFO 队列；但它还必须支持撤掉队列中间任意一笔。普通数组队列做不到 \(O(1)\) 撤单，标准做法是：

• 每个价位一条带哨兵的双向循环链表，新单接到队尾，成交从队头取；
• 一个散列表（下一章）把订单 ID 映射到链表结点的"指针"，撤单时先 \(O(1)\) 查到指针，再 \(O(1)\) LIST-DELETE——这正是 DELETE 接收指针的意义；
• 所有订单结点来自一个预分配的多数组对象池，用自由表分配和回收。

import numpy as np

class OrderPool:
    """多数组表示 + 自由表：预分配 cap 个订单槽，ALLOCATE/FREE 都是 O(1)，运行期不再申请内存。"""
    NIL = -1
    def __init__(self, cap):
        self.oid  = np.full(cap, -1, dtype=np.int64)
        self.qty  = np.zeros(cap, dtype=np.int64)
        self.prev = np.full(cap, -1, dtype=np.int64)
        self.next = np.arange(1, cap + 1, dtype=np.int64); self.next[-1] = -1
        self.free = 0                               # 自由表表头：所有槽初始都空闲
    def allocate(self):
        x = self.free
        if x == self.NIL: raise MemoryError("out of space")
        self.free = self.next[x]                    # 相当于 POP
        return x
    def release(self, x):
        self.next[x] = self.free; self.free = x     # 相当于 PUSH

class PriceLevel:
    """一个价位上的委托队列：带哨兵的双向循环链表（时间优先 FIFO），配合 oid→槽号 的散列表实现 O(1) 撤单。"""
    def __init__(self, pool):
        self.p = pool
        self.nil = pool.allocate()                  # 哨兵也占一个槽
        pool.next[self.nil] = pool.prev[self.nil] = self.nil
        self.index = {}                             # 订单 ID → 槽号（指针）
        self.total = 0
    def add(self, oid, qty):                        # 新委托排到队尾
        p, x = self.p, self.p.allocate()
        p.oid[x], p.qty[x] = oid, qty
        tail = p.prev[self.nil]
        p.next[x], p.prev[x] = self.nil, tail
        p.next[tail] = x; p.prev[self.nil] = x
        self.index[oid] = x; self.total += qty
    def _unlink(self, x):                           # LIST-DELETE'：两行，无边界判断
        p = self.p
        p.next[p.prev[x]] = p.next[x]
        p.prev[p.next[x]] = p.prev[x]
        self.total -= p.qty[x]; del self.index[p.oid[x]]
        p.release(x)
    def cancel(self, oid):                          # 给出 ID → 查表得指针 → O(1) 删除
        self._unlink(self.index[oid])
    def match(self, qty):                           # 市价单从队头开始成交
        p, fills = self.p, []
        while qty > 0 and p.next[self.nil] != self.nil:
            x = p.next[self.nil]
            q = min(qty, p.qty[x]); fills.append((int(p.oid[x]), int(q)))
            qty -= q; p.qty[x] -= q; self.total -= q
            if p.qty[x] == 0:
                self._unlink(x)          # 剩余量为 0，出队并回收槽
        return fills
    def queue(self):
        p, x, out = self.p, self.p.next[self.nil], []
        while x != self.nil:
            out.append((int(p.oid[x]), int(p.qty[x]))); x = p.next[x]
        return out

pool = OrderPool(cap=100_000)
lvl = PriceLevel(pool)
for oid, q in [(101, 300), (102, 500), (103, 200), (104, 400)]:
    lvl.add(oid, q)
lvl.cancel(102)                                     # 撤掉队列中间的单
print("撤单后队列:", lvl.queue(), " 总量:", lvl.total)
print("市价卖 600 股的成交:", lvl.match(600))
print("成交后队列:", lvl.queue(), " 总量:", lvl.total, " 自由表表头槽号:", pool.free)

# 压力测试：随机下单/撤单 20 万次，检查总量一致、没有内存泄漏
rng = np.random.default_rng(0); live = []; nid = 1000
for _ in range(200_000):
    if live and rng.random() < 0.5:
        oid = live.pop(rng.integers(len(live))); lvl.cancel(oid)
    else:
        q = int(rng.integers(1, 10)) * 100; lvl.add(nid, q); live.append(nid); nid += 1
print("在册订单:", len(lvl.index), " 链表合计量 == 记账总量:", sum(q for _, q in lvl.queue()) == lvl.total)
used = 1 + len(lvl.index)                           # 哨兵 + 在册订单
n_free, x = 0, pool.free
while x != -1: n_free += 1; x = pool.next[x]
print("已用槽 + 空闲槽 == 容量:", used + n_free == 100_000)

运行输出：

撤单后队列: [(101, 300), (103, 200), (104, 400)]  总量: 900
市价卖 600 股的成交: [(101, 300), (103, 200), (104, 100)]
成交后队列: [(104, 300)]  总量: 300  自由表表头槽号: 3
在册订单: 75  链表合计量 == 记账总量: True
已用槽 + 空闲槽 == 容量: True

白话解释：把这段代码对应到交易所的真实操作。某只股票 10.00 元的买一档上，四笔买单按到达顺序排队：101（300 股）、102（500）、103（200）、104（400）。这条队就是一个带哨兵的双向循环链表，index 是"订单号 → 槽号"的对照表。投资者撤掉 102：查表得到 102 的槽号，让 101 和 103 直接"拉手"，102 的槽号还回对象池。随后来了一笔 600 股的市价卖单：从队头开始吃，101 吃满 300、103 吃满 200、104 吃掉 100 剩 300，吃满的出队。全程没有任何"挪动后面所有订单"的操作。

读输出时注意几件事：撤掉 102 之后 103 自动"前移"，时间优先关系不变；市价 600 股依次吃掉 101、103 和 104 的一部分，104 留在队头；被成交完的 101、103 的槽号回到自由表，自由表表头变成最近释放的槽 3（栈式复用）。压力测试检查了"每个槽要么在链表里、要么在自由表里"这一不变式。

这个价位队列只是订单簿的一半：订单簿还需要把许多价位按价格排好序，并能快速找到最优价和相邻价位——那是有序动态集合的问题，见本册第 12 章（二叉搜索树与红黑树）。在研究订单簿时，"排在我前面还有多少量"（队列位置）是估计限价单成交概率的关键变量，市场微观结构的讨论见第 07 册。

10.6.3 其他用途

• 事件驱动回测的主循环通常是一个事件队列（FIFO）；当事件带时间戳且可能乱序到达时，要换成优先队列（堆）。
• 因子表达式解析（如 rank(ts_mean(close, 20)) - rank(volume)）要用栈把中缀表达式转为逆波兰式再求值。
• 两个栈实现队列、两个栈实现可查最大值的队列是在线计算滚动聚合的另一种写法，适用于任何满足结合律的聚合（最大值、最小值、矩阵乘积）。

本章小结

本章的几样结构各有分工：栈和队列把"删除谁"固定下来，换来 \(O(1)\) 的插入删除；链表用指针表示顺序，按指针删除 \(O(1)\) 但按关键字搜索 \(\Theta(n)\)，哨兵让代码去掉边界判断；在没有指针或不希望动态分配的场合，多数组表示加自由表能在 \(O(1)\) 内分配回收同构对象；有根树用父/左/右指针或左孩子右兄弟表示。在量化系统中，环形缓冲区与单调队列支撑流式指标，"散列表 + 双向链表 + 对象池"支撑价位委托队列的下单、成交与撤单。

练习

基础

1. 在 \(S[1..6]\) 上依次执行 PUSH(4)、PUSH(1)、PUSH(3)、POP、PUSH(8)、POP，画出每步后的数组和 \(S.top\)。（原书 10.1-1。提示：POP 后元素仍留在数组中。）
2. 用一个数组 \(A[1..n]\) 实现两个栈，使得只要两栈元素总数不到 \(n\) 就都不溢出，操作 \(O(1)\)。（原书 10.1-2。提示：一个从左往右长，一个从右往左长。）
3. 单向链表能否 \(O(1)\) 插入？能否 \(O(1)\) 按指针删除？（原书 10.2-1。提示：插入能；删除需要前驱，一般不能，除非把后继的内容拷到当前结点再删后继——但若后继是表尾就不行，且会让外部持有的指针失效。）
4. 用 \(\Theta(n)\) 时间、常数额外空间、非递归地反转一个单向链表。（原书 10.2-7。提示：三个指针 prev/cur/next 逐个翻转。）
5. 为什么自由表的分配与释放不需要设置 prev 指针？（原书 10.3-3。提示：自由表是单向的，只用 next。）

进阶

6. 用两个栈实现队列，证明 \(n\) 次操作总时间 \(O(n)\)。再进一步：怎样让这个队列还能 \(O(1)\) 回答当前队列中的最大值？（原书 10.1-6 的延伸。提示：每个栈的每个元素同时存"从栈底到它的最大值"；队列最大值 = 两栈栈顶记录的最大值中较大者。）
7. 证明单调队列求滑动窗口最大值的总时间是 \(O(N)\)，并说明为什么"弹出不大于新值的元素"不会丢失答案。（提示：被弹出的元素比新值更早离开窗口且不比它大。）
8. 上面 PriceLevel.match 吃到某笔委托的一部分时不出队，只减少数量。若交易所规定"改单增加数量要重新排队"，应如何用现有操作实现？减少数量是否需要重新排队？（提示：增量改单 = 撤单 + 在队尾新增；减量通常保留原时间优先级。）
9. 思考题 10-3：在紧凑有序链表上先做 \(t\) 次随机跳跃再顺序遍历，证明期望时间 \(O(t+n/t)\)，并解释关键字不互异时为何随机跳跃不一定有帮助。
10. 用左孩子右兄弟表示写一个 \(O(n)\) 的过程，打印任意有根树的所有关键字。（原书 10.4-4。）

原书推荐习题：10.1-2、10.1-5、10.1-6、10.2-4、10.2-7、10.3-4、10.3-5、10.4-3、10.4-5，思考题 10-1、10-3。

原书对照