队列Queue

按先进先出顺序组织待处理元素。

先进先出：当前从队头取出 A；D 入队后排在 C 后面，成为新的队尾。

常见操作#

n 为队列元素数。

操作	时间复杂度	条件与说明
查看队首	$O(1)$	保存队首位置。
入队 / 出队	$O(1)$	带首尾指针的链表或固定容量环形队列；不包含分配和阻塞等待。
动态环形数组入队	摊还 $O(1)$ ；扩容最坏 $O(n)$	按几何比例增长，避免每次出队都移动整个数组。
按值查找 / 遍历	$O(n)$	最坏检查所有待处理元素。

这是队列数据结构的成本；线程安全队列的锁、唤醒与等待时间另计。

2 个案例 · 附源码

Linux Kernel·IIO 软件采样缓冲 / kfifov6.12

Linux IIO 的 kfifo 缓冲在采样进入内核与用户态读取之间暂存数据，按先进先出顺序交付采样记录。

附源码片段 · 内存管理

QEMU·AioContext 线程池v9.2.0

QEMU 线程池用尾队列组织待处理请求：提交时尾插，worker 持锁从头部领取，然后在锁外执行工作。

附源码片段 · 调度与资源分配

基础原理参考资料

Princeton · Queue首尾指针链式 FIFO 队列及各操作成本。

Java 21 · ArrayDeque可用作队列的可增长环形数组实现。