队列

队列保留到达顺序，保持先进先出：最早进入且尚未删除、等待最久的对象最先被服务。这个顺序使它天然表示按发现时间扩张的前沿，而不是任意集合；队头与队尾职责分离，是它与栈的根本区别，也足以支持常数时间入队、出队。数组环形缓冲区通过模容量索引复用已释放位置，避免每次出队搬动剩余元素。

广度优先搜索用队列按距离层次展开顶点。环形缓冲区可在固定数组中复用头部空间，避免每次出队整体移动。优先队列按键而非到达时间删除，因此不是 FIFO 队列。

依次 enqueue $a,b,c$ 后，三次 dequeue 返回 $a,b,c$。长度为 $m$ 的环形数组中，尾指针到末端后回到 $0$；需用元素计数、空一格或额外标志区分“头尾相等表示空”与“表示满”。

队列不支持直接删除中间元素而仍保持同一接口成本。并发队列还需定义原子性和内存回收，单线程指针操作不能直接推广为无锁正确性。

广度优先搜索公理库广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。、任务调度和消息缓冲依赖 FIFO 次序；双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。把合法插入与删除扩展到两端，并可退化为队列或栈。顺序 RAM 中的环形数组可给最坏 $O(1)$ 入队、出队与 $O(n)$ 空间，但这张成本表不属于 FIFO 语义本身。

外存优先队列公理库外存优先队列external-memory priority queue · I/O-efficient priority queue通过批量缓冲、分层下推与最小项物化，以块传输而非逐键访问衡量优先队列操作。按键选择元素并以块传输计费，既不保持到达顺序，也不能用内存队列的常数操作描述。蓄水池抽样公理库蓄水池抽样Reservoir sampling在未知流长度下用 k 个槽维护对已见位置的均匀无放回样本。只需顺序读一次未知长度数据流，却维护的是固定大小均匀样本，不是等待出队的全部元素。并发队列则还需规定线性化点、进展条件与内存可见性；这些结构共享“逐项到达”场景，但接口与保证各不相同。