队列

让最早等待的元素先离开 ​

队列（queue）按照先进先出（FIFO）的规则处理元素：从队尾加入，从队首取出。可以把它想成一列有编号的待处理任务；后来加入的任务排在后面，不能越过仍在等待的旧任务。

这是一个抽象数据类型理路抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。的行为规则，而不是特定内存形状。链表理路链表Linked list通过节点引用保存序列的存储结构；明确前驱、尾指针、节点身份与局部插删的复杂度条件。可以连接队首到队尾，数组也可以借助循环下标复用槽位。与栈理路栈Stack · LIFO stack以栈顶为唯一更新端、按后进先出规则组织元素的抽象数据类型；接口语义与具体表示的成本分别规定。相比，差别在于从哪一端删除，而不在于有没有使用指针。[1]

数组不必每次把元素往前搬 ​

若总让队首占据数组下标 $0$，出队时就要移动整个后缀，一次可能花费 $\mathrm{\Theta }(k)$。循环数组不搬后缀，只移动“队首在哪里”的下标。

取容量 $C>0$，维护队首下标 $h$ 和当前元素数 $s$，不变量为 $0\le h<C$、$0\le s\le C$。第 $j$ 个逻辑元素位于

非满时，入队写入 $A[(h+s)modC]$，再令 $s\leftarrow s+1$。非空时，出队读出 $A[h]$，再令 $h\leftarrow (h+1)modC$、$s\leftarrow s-1$。不再属于队列的槽位可以清除引用，避免无意保留对象。

容量为 $4$ 的一次完整绕回过程如下，— 表示不属于逻辑队列的槽位：

最后一行数组中的物理次序是 E,F,C,D，逻辑次序却仍是 C,D,E,F。循环下标让两者对应，不要求它们看起来一致。

若只存首尾两个模 $C$ 下标，则两者相等既可能表示空，也可能表示满。保存元素数、额外保存满标志，或牺牲一个槽位，都是消除这种歧义的不同约定。本例保存 $s$，因此四个槽位都可使用。[2]

三种常见实现的时间界 ​

固定容量循环数组在非满、非空等相应条件下，可以用最坏 $O(1)$ 的局部操作完成入队、出队和查看队首。若允许几何扩容，复制旧元素的某一次操作会变慢，通常只能对更新声称摊还 $O(1)$；扩容时应按逻辑次序复制，再重新设置队首。

链表实现同时保存头、尾引用。入队接到尾部，出队删除头部，都只修改常数个链接。删除最后一个节点时必须同时把头、尾置空，否则尾引用会指向已经离队的节点。在常数大小节点、局部分配释放按单位成本的模型下，这些操作为最坏 $O(1)$。[1]

队列还可以用两个栈实现：新元素压入输入栈；需要出队且输出栈为空时，把输入栈逐个弹出并压入输出栈，反转后的最旧元素恰好位于输出栈顶。每个元素至多经历一次这样的转移，所以从空结构开始的一串操作总成本为线性，单次出队却可能搬动很多元素。这是摊还常数时间，不是最坏常数时间。

FIFO 在算法里提供了什么 ​

广度优先搜索理路广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。从起点入队开始，每次取出队首，再把尚未发现的邻居加入队尾。只在第一次发现时入队，队列就按距离层次推进：距离为 $d$ 的点扩展时，新发现的点距离为 $d+1$，会排在当前已发现的点之后。这支撑无权图的最短路径结论。

“访问过”的标记通常在入队时设置。若等到出队才标记，多个前驱可能把同一个顶点重复加入，破坏每个顶点只入队一次的时间记账。

任务系统中的FIFO要明确约束的是哪个事件。按FIFO分发给多个工作线程，只保证取任务的次序，不保证任务完成次序；较晚取出的短任务可能先结束。并发实现如Michael–Scott队列理路Michael–Scott 无锁队列Michael–Scott queue · MS queue用哨兵链和可帮助的尾指针修复实现无锁FIFO，并将关键链接、出队与安全回收分别定位。进一步用链接CAS与Head推进定义入队/出队的生效时刻；Tail暂时落后可由别人帮助修复，并不改变抽象FIFO内容。

亏额轮转分组调度理路亏额轮转分组调度Deficit round robin · DRR · 赤字轮转 · 亏空轮询按字节量子和未用余量轮转活跃流，证明持续积压时的服务差界并标出常数调度成本的包长条件。同时使用每流FIFO和活跃流FIFO：一次服务只扣本流头包，未用字节预算保留到下轮，非空流再加入活跃队尾。这样可以在包长不等时讨论字节份额，而不是把“每流一次”误当相等的已发送字节数。

优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。按优先级选择下一项，双端队列理路双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。允许两端操作，二者提供的都不是纯FIFO接口。

循环缓冲区也可结合动态数组理路动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。的扩容策略，但扩容时必须按逻辑队列顺序搬移元素。