Software Systems Atlas

中文

English

中文

English

主题

第 2 卷 / 第 3 章 / 第 3 课

3.3 双端队列：两端操作与滑动窗口 ​

前置：栈、队列。这一节先辨清四种端点操作，再处理 maxlen 与 extendleft 的边界，最后用单调 deque 把滑动窗口最大值降到 Θ(n)。

两个端点的操作合同 ​

双端队列（double-ended queue，通常读作“deck”）开放两端。它有四项基本修改操作：

方向放入取出
左端 / 队首appendleft(x)popleft()
右端 / 队尾append(x)pop()

栈只暴露一端的 LIFO 用法；队列固定从尾部进入、头部离开的 FIFO 用法；deque 把四种端点操作都交给调用者。一个 deque 可以承载栈或队列的行为，但“数据结构能实现某种契约”不等于这些抽象是同义词。

Python deque 的成本边界 ​

Python collections.deque 文档把两端追加和弹出描述为近似 O(1)。它适合工作队列、最近记录、双向扫描和单调队列。

它不是随机访问列表的通用替代：

  • d[0] 与 d[-1] 访问两端是 O(1)；
  • 向中间移动的索引访问会变慢，最坏为 O(n)；
  • insert、remove、index 等涉及查找或内部位置的操作也不属于四项端点保证。

如果主要操作是按下标读取或修改中间元素，list 通常更贴近需求。出现 list.pop(0) 或 list.insert(0, x) 是重新评估容器的信号，还要结合队列规模、操作频率和接口约束决定是否改用 deque。

四个端点操作跑一遍 ​

下面的完整程序先验证四项端点操作，再运行滑动窗口算法：

python
from collections import deque
from operator import index as integer_index

def max_sliding_window(nums, k):
    k = integer_index(k)
    if not 1 <= k <= len(nums):
        raise ValueError("k must satisfy 1 <= k <= len(nums)")

    candidates = deque()
    maxima = []
    for index, value in enumerate(nums):
        while candidates and candidates[0] <= index - k:
            candidates.popleft()
        while candidates and nums[candidates[-1]] < value:
            candidates.pop()
        candidates.append(index)
        if index >= k - 1:
            maxima.append(nums[candidates[0]])
    return maxima

if __name__ == "__main__":
    jobs = deque()
    jobs.append("任务 B")
    jobs.append("任务 C")
    jobs.appendleft("任务 A")
    jobs.appendleft("紧急任务")

    print(f"双端结果：{list(jobs)}")
    print(f"左出：{jobs.popleft()}")
    print(f"右出：{jobs.pop()}")

    values = [1, 3, -1, -3, 5, 3, 6, 7]
    print(f"窗口最大值：{max_sliding_window(values, 3)}")

    assert list(jobs) == ["任务 A", "任务 B"]
    print("双端队列检查通过")
text
双端结果：['紧急任务', '任务 A', '任务 B', '任务 C']
左出：紧急任务
右出：任务 C
窗口最大值：[3, 3, 5, 5, 6, 7]
双端队列检查通过

前四次写入得到：

text
左端                                             右端
紧急任务 <- 任务 A <- 任务 B <- 任务 C

popleft 取走紧急任务，pop 取走任务 C，内部还剩任务 A 和任务 B。deque 不替你决定“哪端代表队首”，这个含义由当前算法的契约决定。

有界 deque：满时会发生什么 ​

创建 deque(maxlen=n) 可以把元素数量限制在 n 以内：

python
from collections import deque

recent = deque(["事件 1", "事件 2"], maxlen=3)
recent.append("事件 3")
recent.append("事件 4")

assert list(recent) == ["事件 2", "事件 3", "事件 4"]
assert recent.maxlen == 3

队列已满时从右端 append，Python 会丢弃左端元素；从左端 appendleft，则丢弃右端元素。这适合“只保留最近 N 条”的契约，却不适合不能静默丢数据的任务队列。

还有一个容易漏掉的差异：对已满的有界 deque 执行 insert(index, value)，若插入会超过 maxlen，它抛出 IndexError，不会自动从另一端腾位置。maxlen=0 合法，追加后仍为空；负的 maxlen 会抛 ValueError。

python
from collections import deque

right_append = deque([1, 2, 3], maxlen=3)
right_append.append(4)
assert list(right_append) == [2, 3, 4]

left_append = deque([1, 2, 3], maxlen=3)
left_append.appendleft(0)
assert list(left_append) == [0, 1, 2]

extendleft 会反转输入顺序 ​

extendleft 等价于连续执行多次 appendleft：

python
from collections import deque

letters = deque(["d"])
letters.extendleft(["a", "b", "c"])

assert list(letters) == ["c", "b", "a", "d"]

先把 a 放到左端，随后 b 又站到 a 左边，最后 c 站到最左边，因此输入次序在 deque 中反转。若要在左端保持原迭代顺序，若 items 是列表等可反向遍历的序列，可传入 reversed(items)；普通单次迭代器需要先缓存。

python
from collections import deque

def is_palindrome(text):
    chars = deque(char.lower() for char in text if char.isalnum())
    while len(chars) > 1:
        if chars.popleft() != chars.pop():
            return False
    return True

assert is_palindrome("Never odd or even")
assert not is_palindrome("river")

这里的回文函数保留 isalnum() 字符，再逐字符调用 lower()；空串或全是标点时返回 True。它演示两端配对，不完整处理 Unicode 规范化、跨字符大小写映射或字素簇。扫描和构建 deque 最坏都需 Θ(n) 工作与存储。

用 deque 维护滑动窗口最大值 ​

给定数组和宽度 k，窗口每右移一格就报告当前最大值。

暴力方法为每个窗口重新扫描 k 个元素，时间是 Θ((n-k+1)k)，常写成 O(nk)。单调 deque 保存“仍可能成为未来最大值”的索引，把总成本降到 Θ(n)。

三条不变量 ​

处理完当前下标 i 后（前几轮尚未形成完整窗口）：

  1. deque 中只保留当前窗口 [i-k+1, i] 内的索引；
  2. 对应值从队首到队尾单调不增；
  3. 队首索引对应当前窗口最大值。

示例代码先移除已经离开窗口的队首，再从队尾移除严格小于新值的候选。相等值不会被这段实现提前删除，它们按索引先后保留；旧的相等值离开窗口后，新的仍可接替。

为什么较小的队尾可以删除 ​

假设索引 j < i，且 nums[j] < nums[i]。新元素 i 更靠右、值又更大。在任何同时包含二者的未来窗口里，j 都不可能成为最大值；当 i 离开窗口时，j 早已离开。因此可以永久删除 j。

手算前几个窗口 ​

数组是 [1, 3, -1, -3, 5, 3, 6, 7]，k=3：

读到下标当前值候选索引（队首 → 队尾）已形成窗口的最大值
01[0]尚未满
13[1]尚未满
2-1[1, 2]3
3-3[1, 2, 3]3
45[4]5
53[4, 5]5

每个索引入队一次。它最多因为过期从左端出队一次，或因为被更大元素支配从右端出队一次，所以总操作数与 n 成正比。候选最多 k 个，辅助空间为 O(k)；返回的 n-k+1 个最大值另占 Θ(n-k+1) 输出空间。

输入边界 ​

本节要求 nums 支持常数时间索引，元素比较为常数成本且有一致的全序；含 NaN 等不遵守这个次序的值不在输入合同内。k 必须是满足 1 <= k <= len(nums) 的整数。非整数抛 TypeError，空数组、k=0 或 k>n 抛 ValueError。其他接口也可以为这些无效窗口返回空列表，但代码与测试必须遵守同一约定。

选 deque 还是 list ​

工作负载更合适的起点原因
右端追加、右端弹出list 或 deque两者都支持高效端点操作
左右两端频繁追加和弹出deque四项端点操作都有直接接口
大量按下标随机访问listdeque 的中部索引为 O(n)
固定保留最近 N 项deque(maxlen=N)内建有界淘汰语义
在任意中间位置频繁修改先重新审视算法deque 不保证中间操作常数时间

这张表给出起点，不替代测量。元素规模、内存占用、并发契约和库版本都会影响实际选择。

Python、Java、C++ 的 deque 接口 ​

语言类型左加 / 左取右加 / 右取重要边界
Pythoncollections.dequeappendleft / popleftappend / pop两端近似 O(1)；中部索引 O(n)；可设置 maxlen
Java 17Deque<E> / ArrayDeque<E>offerFirst / pollFirstofferLast / pollLastArrayDeque 禁止 null、非线程安全；大多数操作均摊常数时间
C++std::deque<T>push_front / pop_frontpush_back / pop_back支持随机访问；单个元素的端点插入删除为常数时间，内部布局由实现管理

Java Deque 为每项操作提供两类形式：一类失败时抛异常，另一类返回特殊值。作为栈使用时，push/pop/peek 对应首端；作为 FIFO 队列使用时，offer/poll/peek 从尾部加入、首端取出。

Python 文档保证单次两端追加与弹出的线程安全，但 if d: d.popleft() 仍是两个步骤，不是原子协议。C++ std::deque 的两端插入保留已有元素引用，却会使迭代器失效。接口名字相近，不代表布局、句柄稳定性或并发保证相同。

参考契约：

常见错误怎么定位 ​

症状先检查什么
把队首队尾写反在接口旁明确标注每个方向的业务含义
有界 deque 悄悄丢任务maxlen 淘汰是否符合业务契约
extendleft 结果逆序是否需要 reversed(items)
窗口最大值使用了过期元素新一轮是否先检查 dq[0] <= i-k
重复最大值离开后答案错误deque 是否保存索引；相等值采用什么删除策略
用 deque 中间索引后变慢是否把随机访问工作负载误交给 deque

动手维护单调候选 ​

  1. 从空 deque 依次执行 append(1)、appendleft(2)、pop()、popleft()，每步状态是什么？
  2. 对 deque([1, 2, 3], maxlen=3) 调用 appendleft(0) 后，容器内容是什么？方法本身返回什么？
  3. 给 extendleft(["a", "b"]) 画出每次插入后的顺序。
  4. 手算数组 [4, 2, 2, 5]、k=2 的候选索引和答案。
  5. 修改滑动窗口算法，让相等值只保留较新的索引。应该把 < 改成什么？结果会变吗？

比较三类线性容器 ​

双端队列的核心是高效的两端操作，方向由算法决定。作为栈使用时，两项操作落在同一端；作为 FIFO 队列使用时，从一端进入、另一端离开；作为单调队列使用时，还要维护“索引未过期、值单调不增”两条状态约束。maxlen 的静默淘汰也只有在业务允许丢弃旧数据时才合适。

栈、队列与 deque 的接口和成本已经可以放在同一张表里比较。下一章进入哈希表，研究怎样根据 key 缩小候选位置。

Built with VitePress | Software Systems Atlas

Copyright 2026 Steven Yang