队列

队列从尾部加入元素，从头部取出元素，遵循先进先出（FIFO）。enqueue 入队，dequeue 出队；加入顺序就是取出顺序。

排队买咖啡时，新来者站在队尾，队首先接受服务。调度器、消息缓冲区、打印队列和广度优先搜索都会用这种规则管理等待的工作。

队列如何工作

enqueue(val) 在尾部加入 val，dequeue() 删除并返回头部元素。本课实现有容量上限：已有 max 个元素时入队，抛出 Queue Full；空队列出队，抛出 Queue Empty。这两项检查存在于展示的代码中，入队被拒绝时不修改队列。

栈在同一端加入和取出，队列使用两端。改错其中一端，就会改变 FIFO 与 LIFO 的行为。

展示代码用普通 Python 列表存储，以 pop(0) 出队。其余元素都要向左移动，因此出队是 O(n)。这是实现成本，不是 FIFO 的要求。环形缓冲区用首尾索引在数组中循环，collections.deque 也支持 O(1) 的两端操作。

逐步演示

默认队列为空，容量为 8。在输入面板运行：

1. enqueue(3)：得到 [3]，队首和队尾是同一元素。
2. enqueue(7)：得到 [3, 7]。
3. enqueue(1)：得到 [3, 7, 1]。
4. dequeue()：返回最先加入的 3，剩下 [7, 1]。
5. dequeue()：返回 7，剩下 [1]。
6. dequeue()：返回 1，恢复 []。

默认演示到这里结束。再出队一次，会抛出 Queue Empty，状态不变。取出顺序 3、7、1 与加入顺序相同，这是规则保证的结果。

画布的 FRONT 箭头指向第一个格子，BACK 跟随最后一个格子。出队元素从左侧离开，其余格子左移一格。标题中的 size、front、back 随每步更新，对应上面的状态序列。

时间与空间复杂度

FIFO 规定顺序，具体成本取决于存储方式。

列表和 deque 保存 n 个等待元素，空间为 O(n)。定容为 C 的环形缓冲区预先分配全部 C 个槽位，无论等待多少个，空间都是 O(C)。

边界情况

• 满队列入队：检查 max 后抛出 Queue Full。有界队列可用于施加背压；滑块最多 10 则只是画布宽度限制。
• 空队列出队：本课抛出下溢异常，调用前检查或捕获即可。其他 API 也可能返回哨兵值，取决于空队列是否属于预期流程。
• 单个元素：队首与队尾重合，出队后变空。
• 只出不进：依次重放加入顺序，清空后再出队就下溢。

常见错误

• 把 pop(0) 当成常数时间。 它要移动元素。队列规模增大时可用 collections.deque。
• 从队尾出队。 会变成栈，程序不一定报错，但 FIFO 已失效。
• 把优先队列当普通队列。 优先队列按优先级服务，常用堆实现，不保证最早到达者先出。
• 用两个栈实现队列时频繁倒栈。 只有输出栈为空时才从输入栈补充，才能保持摊还 O(1)；每次出队都搬运会花 O(n)。