队列
队列遵循先进先出（FIFO）原则：元素从尾部入队，从头部出队或查看。
from collections import deque
queue: deque[str] = deque()
queue.append("first")
queue.append("second")
front = queue[0]
removed = queue.popleft()
deque 在两端操作上都具备高效性能。相比之下，Python 的 list.pop(0) 需要移动后续所有引用，时间复杂度为 ，因此不适合用作默认的队列操作。
实现方式
- 链式端点：维护头尾节点指针。只要不变量正确，入队和出队操作均为 。
- 环形缓冲区：在固定数组中存储元素，通过头指针和大小/尾指针（对容量取模）来管理。有界操作无需移动元素，复杂度为 。
- 可扩容双端队列：采用分块或环形存储结构，在动态扩容的同时保持两端访问的高效性。
不变量与策略
空链式队列通常头尾指针均未设置。环形缓冲区必须通过记录大小、预留一个槽位或等效的不变量机制，来明确区分“空”和“满”的状态。
下溢（空队列出队）和满容量（满队列入队）时的行为属于接口设计的一部分：可以选择抛出异常、阻塞等待、丢弃数据、覆盖旧数据或施加背压。在并发和异步系统中，这些策略的选择往往比基本的 FIFO 规则更关键。
应用场景与边界
队列是广度优先搜索（BFS）、事件循环、数据缓冲和工作调度的核心组件。注意，优先队列（Priority Queue）不同，它按优先级而非到达顺序移除元素。此外，线程/进程安全的消息队列还涉及同步机制和投递语义，这超出了纯内存 ADT（抽象数据类型）的范畴。
环形缓冲区怎样绕回开头
容量 C 必须为正。维护下次出队的位置 head 和元素数 size，满足 0 <= size <= C。逻辑位置 i 对应物理槽位 (head + i) % C。未满时，入队先写入 (head + size) % C，再把 size 加一；非空时，出队先读取并清空 head 槽位，再令 head = (head + 1) % C，并把 size 减一。清空槽位可以释放容器对已移除对象的引用。
容量为 3 时，把 A、B、C 依次写入槽位 0、1、2。移除 A 后，head = 1、size = 2。再把 D 写入 (1 + 2) % 3 = 0。物理槽位依次是 D、B、C，逻辑顺序却是 B、C、D。即使头位置与下次写入位置重合，也能用大小区分空与满。这就是数组队列的索引机制；扩容会增加复制，并改变单次操作的成本保证。
Python 的容量行为
开头示例中的 front 和 removed 都是 "first"，剩余元素是 "second"。对空队列执行 queue[0] 或 queue.popleft() 会抛出 IndexError。deque 文档规定，有界双端队列的追加操作采用另一种满容量策略：
recent = deque(["A", "B"], maxlen=2)
recent.append("C")
assert list(recent) == ["B", "C"]
这里会主动丢弃 A，适合保存最近记录，不适合必须保留每个任务的工作队列。单靠 deque 也不能让“先判空，再移除”这组操作成为原子操作。需要让生产者或消费者阻塞等待时，应使用为这种协作设计的队列接口。