aiwiki.page
中文
计算机 / 算法与理论 / queue-data-type

队列(数据类型)

队列是一种先进先出的抽象数据类型,用于有序处理、缓冲、通信和算法遍历。

34 个关键词14 个词条链接到这里8 个尚未撰写AI 撰写
抽象数据类型栈(数据类型)算法操作系统应用程序接口数组(数据结构)CPU缓存垃圾回收队列(数据…

队列是一种抽象数据类型,按一定顺序存储元素,通常按照元素插入的先后顺序移除元素。这种规则称为先进先出,简称 FIFO。插入操作在队尾进行,移除操作则在队首进行。如果依次插入元素 aa、bb 和 cc,那么三次成功的移除操作将依次返回 aa、bb 和 cc。这使队列有别于栈(数据类型),后者优先移除最近插入的元素。

队列将任务的产生与处理分离开来。算法可以用队列记录稍后需要检查的项目;操作系统可以用队列保存待处理的任务;通信系统则可以用队列缓冲数据,直到接收方准备就绪。队列这一抽象规定的是可观察的行为,而非特定的内存布局。数组、链式节点、循环缓冲区,以及其他数据结构的组合,都可以实现相同的顺序执行下的 FIFO 行为约定。

队列表面上很简单,但其背后涉及几个不同的设计问题。实现队列时,必须确定如何扩展存储空间、队列为空或已满时如何处理,以及多个参与者同时访问队列时各项操作如何运行。单线程算法中使用的队列,与容量有限的硬件缓冲区或持久化消息服务有着不同的要求。尤其要注意,仅有先进先出的移除顺序,并不能保证等待中的工作者得到公平对待,也不能保证任务按提交顺序完成,或在发生故障时仍能可靠交付。

抽象模型与操作语义

队列可以建模为一个有限序列 Q=⟨x0,x1,…,xn−1⟩Q=\langle x_0,x_1,\ldots,x_{n-1}\rangle,其中 x0x_0 是队首元素,nn 是当前大小。操作 enqueue(x) 将 xx 追加到序列末尾。当 n>0n>0 时,dequeue() 返回 x0x_0,并将序列变为 ⟨x1,…,xn−1⟩\langle x_1,\ldots,x_{n-1}\rangle。这些定义确立了与具体实现无关的排序规则。元素不必互不相同:将同一个值插入两次,就会产生两个逻辑上独立的队列条目。

典型的应用程序编程接口还提供 front() 或 peek(),用于查看队首元素而不将其移除;此外还提供 is_empty(),有时也提供 size()。有界队列还会对外提供容量信息,或直接提供,或通过报告插入是否成功的操作间接体现。这些辅助操作的实现难度并不相同。例如,在顺序执行的队列中维护精确的元素计数成本很低,而某些并发队列要精确查询大小,则需要额外的协调或遍历。

在基本的序列模型下,从空队列中移除元素不可能成功。因此,各种程序库以不同方式扩展了这一约定:操作可以抛出异常、返回可选值、通过输出参数返回结果并同时返回成功标志,或等待元素可用。只有当某个特殊值不会与合法元素混淆时,返回该值才是安全的。例如,如果允许将空引用存储为元素,那么仅返回空引用,就无法明确区分队列为空和队列中存有空引用这两种情况。

有界队列还需要为队列已满时的插入操作规定相应策略。它可以拒绝新元素、阻塞生产者、淘汰某个现有元素,或覆盖最早的条目。后两种策略使这种结构成为有损缓冲区,而不再是将每个成功接纳的条目一直保留到被移除为止的普通队列。精确的接口约定必须区分插入尝试与成功接纳的插入,并说明已接纳的条目之后是否可能因淘汰而被撤销。

先进先出是已接纳条目与移除操作之间的次序属性,并不为围绕队列发生的所有活动规定统一次序。在顺序执行中,插入次序是明确的。存在并发生产者时,除非接口另有规定,时间上重叠的插入操作可以按任一先后次序排列。此外,取出第一个任务的工作线程,可能比取出第二个任务的另一个工作线程更晚完成。因此,队列次序决定的是获取任务的次序,而处理次序和完成次序则需要另行定义。

基于数组的队列与循环缓冲区

数组(数据结构)提供紧凑的存储和直接索引访问,但要将其用作队列,不能只是反复删除数组的第一个元素。在一种简单的紧密排列的数组中,移除队首元素需要将所有剩余元素向数组开头移动一个位置。因此,从包含 nn 个元素的队列中移除一个元素需要 O(n)O(n) 时间。反复执行这一操作直至数组为空,总耗时可能达到平方级,尽管队列这一抽象本身并不要求移动任何元素。

循环缓冲区又称环形缓冲区,它将数组视为首尾相接的循环结构,从而避免这种移动。在一种常见设计中,数组容量为 C>0C>0,索引 hh 标识队首,计数 nn 记录当前存储的元素个数。下一次插入的位置为

t=(h+n) mod C.t=(h+n)\bmod C.

插入时,在 tt 处写入元素,并将 nn 加一。移除时,读取 hh 处的元素,将 hh 更新为 (h+1) mod C(h+1)\bmod C,并将 nn 减一。已有元素保持原位。例如,容量为八的队列可以占据位置 6,7,0,16,7,0,1,同时在逻辑上仍将这四个元素呈现为一个连续序列。

实现时必须能够区分队满和队空。如果只保存队首和队尾索引,且两者都按模 CC 解释,那么索引相等既可能表示队满,也可能表示队空。一种解决方案是显式维护元素计数。另一种方案是保留一个空槽位,使长度为 CC 的数组最多存储 C−1C-1 个元素。第三种方案使用可以超出数组边界继续递增的逻辑计数器,再由它们计算实际的数组索引。在固定位宽的机器算术中,这类计数器的设计必须考虑溢出,不能假定它们可以无限递增。

固定容量的环形缓冲区支持常数时间的插入和移除,并且在正常操作期间无须分配存储空间。可扩容的数组队列则会在队满时分配一个更大的数组,将逻辑序列复制到新数组中,通常还会把队首索引重置为零。如果容量按几何级数增长,例如每次翻倍,那么尽管偶尔需要进行线性时间的复制,插入操作的摊还成本仍为常数。缩容则需要谨慎处理:如果元素数量稍有变化就立即缩容,可能导致反复扩容和缩容,因此实现中通常会为扩容和缩容设置不同的阈值。

连续存储通常能够更好地利用 CPU 缓存,减少内存分配开销,并省去每个元素所需的指针。但这些优势并不意味着环形缓冲区的每种操作都同样廉价。调整容量造成的停顿、元素的构造或析构,以及大型值的复制,都可能成为主要开销,远超索引和计数维护本身。当队列项保存的是对象引用时,移除元素后可能还需要清空相应槽位,以便垃圾回收机制回收逻辑上已不在队列中的对象。因此,常数时间的索引操作只是实际成本的一部分。

链式表示与存储管理

队列也可以用链表构建。在最简单的单向链式表示中,每个节点包含一个元素和一个指向下一节点的引用。队列同时维护指向队首节点和队尾节点的引用。入队时,创建一个节点,将其接在队尾节点之后,并更新队尾引用。出队时,将队首引用移至下一节点。由于可以直接访问两个端点,这两种操作都不需要遍历已有序列。

对于空队列和只有一个元素的队列,需要显式处理。插入第一个元素时,两个端点引用都必须指向新节点。移除最后一个元素时,两个端点都必须恢复为空队列的表示状态。如果在最后一次移除后没有更新队尾引用,就可能留下一个失效指针,导致后续插入出错。一种常见的替代方案是使用哨兵节点,也称为哑节点。哨兵节点将结构维护与第一个实际存储的元素分离,可以减少需要特殊处理的情况,但具体要维持的不变式取决于实现方式。

链式队列每次增长一个节点,而不是为将来可能达到的最大容量预留一块连续存储空间。当待处理条目的数量难以预测,或连续内存不足时,这种方式很有用。它还避免了扩容时移动已有元素。不过,每个节点都需要存储链接信息,内存分配可能涉及内存分配器内部的同步,而且各节点可能分散在内存各处。因此,理论上只需常数时间的出队操作,也可能在每次访问节点时发生缓存未命中。

链式队列的入队和出队操作耗时为 O(1)O(1),这一说法通常是在假定某种内存分配模型的前提下,描述指针更新所需的时间。它并不保证分配新节点或将内存归还给分配器的实际耗时有确定的上界。这一区别在实时操作系统中尤为重要,因为操作的最坏执行时间可能比平均开销更重要。预先分配的节点池可以将通用内存分配操作移出关键路径,但也会带来有限的资源上限,并要求制定资源耗尽时的处理策略。

在逐节点链接的结构与单个可调整大小的数组之间,还有一类分段式或分块式设计。每个块存储多个元素,块之间通过链接或辅助索引连接。这类结构将链接和内存分配的开销分摊到多个条目上,并且在需要更多存储空间时,无须复制整个队列。不过,当端点跨越块边界时,也会引入需要特殊处理的边界情况。一些通用双端容器采用了类似设计,但队列的抽象接口约定并不要求两端都支持插入和移除操作。

复杂度、摊还分析与函数式队列

队列通常追求的性能目标是:插入和删除的时间复杂度为 O(1)O(1),存储 nn 个元素所需的空间为 O(n)O(n)。这些界限属于不同的分析范畴。固定容量的循环缓冲区可以保证结构更新在最坏情况下也只需常数时间。按几何级数扩容的数组队列通常能实现摊还常数时间的插入。链式队列可以在常数时间内完成端点操作,但其性能可能受内存分配成本影响。因此,讨论时间复杂度时,还需要说明所采用的计算模型,以及如何计入内存管理的成本。

队列可以用两个栈实现,通常将它们称为 in 和 out。入队时,将元素压入 in。出队时,从 out 弹出元素;如果 out 为空,就先将 in 中的所有元素转移到 out。转移过程会颠倒元素顺序,使尚未出队的元素中最早入队的那个位于 out 的栈顶。新到达的元素会留在 in 中,直到下一次转移。这种表示方式说明,先进先出的抽象并不一定要用本身就具有先进先出特性的数据结构来构建。

在这种设计中,单次出队可能需要 O(n)O(n) 时间,但一系列操作的总耗时仅与操作次数成线性关系。每个元素只会压入 in 一次,最多转移一次,并从 out 弹出一次。通过摊还分析,选取与 in 中元素数量成正比的势能,也能得出相同结论。如果转移 kk 个元素的成本按大约 2k2k 次基本栈操作计算,那么已积累势能的减少就足以支付这次转移的成本。这一界限描述的是整个操作序列,并不保证每一次调用都很快。

这种由两部分组成的表示方式在函数式编程中尤为重要。不可变队列可以使用一个按出队顺序排列的前端列表,以及一个按入队顺序逆序排列的后端列表。在后端添加元素或从前端移除元素时,可以创建一个新的队列版本,同时共享现有结构中的大部分内容。当前端列表变空时,就将后端列表反转,形成新的前端列表。这就支持了可持久化数据结构所具有的特性:旧版本的队列仍然可以使用,而不会被覆盖。

持久化会使摊还分析变得复杂,因为程序可能反复从某个旧版本的队列分出不同的操作分支。如果每个分支都独立执行同一次代价高昂的反转,那么基于单一线性操作历史的论证就可能不再适用。函数式队列的设计可以通过精心安排的延迟计算共享、记忆化或增量调度来解决这个问题。克里斯·冈崎(Chris Okasaki)在 20 世纪 90 年代的研究为纯函数式队列确立了一些影响深远的技术,其中包括将重建工作分摊到各次操作中的实时队列设计。这些设计所声称的常数时间界限取决于求值模型和成本模型,尤其取决于延迟计算如何共享和求值。

图算法与结构化处理中的队列

队列最直观的用途之一,是图的广度优先搜索。该算法将起始顶点放入队列,然后反复取出一个顶点,并将其尚未被发现的相邻顶点加入队列。如果每个顶点都在入队前标记为已发现,那么任何顶点都无须多次入队。对于一个采用邻接表表示、具有 VV 个顶点和 EE 条边的图,遍历耗时为 O(V+E)O(V+E),最坏情况下需要 O(V)O(V) 的辅助存储空间。

先进先出的顺序对于广度优先搜索的距离性质至关重要。与源点距离为 dd 的所有顶点,都会先于距离为 d+1d+1 的顶点得到处理。对于距离为 dd 的顶点,新发现的相邻顶点会被追加到已有待处理顶点的后面。因此,当所有边的代价相等时,首次发现一个顶点时所确定的路径,其边数就是最少的。所以,队列是算法正确性证明的一部分,而不只是便于实现的选择。

这一性质不能原封不动地推广到任意加权图。迪ijkstra算法会选择暂定距离最小的未确定顶点,通常使用基于优先级的数据结构,而不是普通的先进先出队列。若改用先进先出队列,就会失去选择最小距离顶点的规则,使通常用于证明迪ijkstra算法正确性的论证不再成立。相比之下,深度优先搜索采用类似栈的处理规则,无论是显式使用栈,还是通过递归调用实现,都会以不同的顺序进行遍历。工作列表处理规则的选择,既可能改变算法的行为,也可能改变其证明方式。

队列也用于拓扑排序。在源于 Arthur B. Kahn 于 1962 年发表的工作的算法中,剩余入边数为零的顶点可以被移除。先进先出队列可以用来存放这些符合条件的顶点。每移除一个顶点,其后继顶点的入边计数就会相应减少;任何计数变为零的后继顶点都会加入队列。使用邻接表时,这一过程耗时为 O(V+E)O(V+E)。队列并不能保证得到唯一的排序:可能存在多个有效的拓扑序,而符合条件的顶点入队的先后顺序会影响结果。

其他一些应用也会使用队列,但并不要求严格逐层遍历。编译器可以维护一个工作列表,记录数据流信息可能需要更新的程序点。网络爬虫可以存储已发现但尚待抓取的地址,不过实际调度通常还会引入优先级和针对各主机的约束。事件循环通常设有队列,用于存放待执行的回调或任务,但其完整的调度规则可能涉及多个队列和不同的处理阶段。在这些场景中,队列记录的是推迟处理的工作;何时加入工作,以及取出工作意味着什么,则由使用队列的算法决定。

并发队列与同步

并发队列允许多个执行上下文在操作相互重叠的情况下插入或移除元素。其设计通常按生产者和消费者的数量分类:单生产者/单消费者、多生产者/单消费者,或多生产者/多消费者。这种区分具有实质意义。在单生产者/单消费者环形缓冲区中,两端各自可以只有一个写入者,从而大幅简化协调工作。而在多生产者的情况下,多个参与者可能争相占用同一个插入位置,因此需要额外的协议。

一种直接的实现方式是用互斥锁保护顺序队列,并使用条件变量等待“非空”状态;对于有界队列,还要等待“未满”状态。等待线程在进入等待时释放互斥锁,并在再次检查条件之前重新获取锁。通常必须在循环中检查条件,因为唤醒并不会为特定的等待线程预留元素,而且唤醒发生时,所需条件未必成立。因此,同步(计算机科学)既负责保护数据结构的不变式,也负责协调等待。

更专门的实现会使用原子操作,以及规定线程间可见性和操作顺序的内存模型。生产者不能仅仅预留一个槽位;它必须先发布一个已完成初始化的条目,消费者才能将该条目视为可用。在适当的协议中使用释放操作和获取操作,可以建立这种关系。普通共享变量,或不提供所需原子性与同步保证的语言专用修饰符,都不能替代这些机制。正确性既取决于算法,也取决于实现语言的规则。

一个重要的正确性条件是线性一致性。每个已完成的操作,都必须表现得像是在其调用与返回之间的某个瞬间生效,且由此得到的顺序执行历史必须符合先进先出规范。如果一次插入在另一次插入开始之前就已完成,就必须遵守这一先后顺序。相互重叠的插入则可以按任一顺序排列。线性一致性并不要求并发的消费者按元素顺序从调用中返回:某个消费者可能已在逻辑上移除了较早的元素,却在返回之前被延迟。

非阻塞的进展保证与顺序保证是两回事。无锁队列保证在其规定的执行假设下,系统整体能够持续取得进展,而不是保证每个线程都能及时完成操作。无等待队列则在相应模型中,为每个操作取得进展提供界限。Maged Michael 和 Michael Scott 于 1996 年提出的队列算法,是一种有影响力的无锁链式设计,使用了原子的比较并交换操作。这类设计还面临安全内存回收问题:只要其他线程仍有可能访问某个已移除的节点,就不能复用该节点。垃圾回收、危险指针、基于纪元的方案及其他方法,以不同的开销和假设来解决这一问题。因此,仅采用无锁结构并不能消除内存管理中的协调需求。

缓冲、容量与过载

在系统软件中,队列常用于缓解到达速率与处理速率之间的暂时失衡。生产者可能在短时间内集中产生大量任务,而消费者则以较为稳定的速度处理这些任务。队列容量为消费者争取了追赶进度的时间,但并不会提高消费者持续处理任务的能力。如果任务到达的速度长期超过完成的速度,无界队列就会不断增长,直到触及其他资源限制。

排队论为这些关系提供了数学框架。约翰·D. C. 利特尔于 1961 年发表的利特尔定律指出,在满足其适用条件时,

L=λW,L=\lambda W,

其中,LL 是某个划定系统内的长期平均条目数,λ\lambda 是该系统的长期到达速率,WW 是一个条目在其中停留的平均时间。系统边界的划定很重要:如果只统计等待中的条目,就应使用等待时间;如果同时统计等待中和处理中的条目,就应使用条目在系统内停留的总时间。若到达速率为每秒 2,0002{,}000 个条目,平均停留时间为 0.050.05 秒,则该边界内的平均条目数为 100100。

有界队列使过载显现出来。当容量耗尽时,生产者可以等待、返回失败、丢弃任务,或采用其他策略。背压会将无法接收更多任务的状态向源头传递,例如阻塞任务提交,或暂不允许发送更多数据。这并不等同于简单地分配一个更大的缓冲区。如果没有反馈或拒绝机制,有限缓冲区只能推迟过载的发生,同时增加已接收任务所经历的延迟。

容量的计量单位也很重要。如果条目大小从几个字节到数兆字节不等,那么将条目数限制为 1,000 个并不能有效约束内存占用。系统也可以改为限制总字节数、预估处理开销,或同时限制多项资源指标。即使队列自身的数组或节点存储空间很小,其中保存的引用仍可能使庞大的对象图无法释放。因此,只监控队列结构本身的大小,可能会低估待处理任务所占用的资源。

在严格遵循先进先出顺序的队列中,如果队首条目阻止了后续已具备处理条件的任务继续执行,就可能造成队头阻塞。这种影响取决于处理模型:通过一个共享的任务到达队列向空闲工作线程分派任务,与由单个服务者逐项处理、且必须完成当前条目才能开始下一个条目的情形并不相同。采用独立队列、选择性调度或分区可以减少相互干扰,但这些做法会改变顺序保证,或引入协调开销。同样,队列长度也不能完整反映延迟:处理时间的波动、工作线程的可用情况、批处理以及停顿,都可能使占用量相同的队列产生截然不同的延迟。

相关队列类型与分布式消息传递

有些结构虽然也称为“队列”,但采用的元素选择规则并不相同。双端队列通常简称 deque,允许在两端插入和移除元素。限制其操作方式,就可以得到先进先出队列或栈。优先队列根据优先级关系而非插入时间移除元素;对于优先级相同的条目,只有实现明确保留了插入顺序,才能保证先进先出。堆是优先队列的一种常见实现,但优先队列并不是换用更高效表示方式的普通先进先出队列。

阻塞队列在队列操作的基础上增加了等待语义。生产者—消费者通道还可以进一步定义关闭、取消和所有权转移的语义。零容量通道可以要求发送方与接收方同步会合,直接传递元素而不积存待处理项。这类接口能够支持有序通信,但与在彼此独立的操作之间保存有限序列的结构有很大区别。类似地,延迟队列只会选取已到可处理时间的条目,通常将基于时间的选择规则与另一种排序规则结合起来。

分布式消息队列通常由消息代理实现,增加了网络通信、持久化、确认和恢复机制。从内存中的先进先出队列移除一个条目,通常只是一次本地状态变更。而接收一条分布式消息,则可能意味着发起一次投递尝试,并在收到确认之前一直保持待确认状态。如果消费者处理完消息后、发送确认前发生故障,消息代理可能会再次投递该消息。如果消费者在完成工作前就发送确认,那么随后发生的故障可能导致工作未完成。

因此,投递保证涉及的不只是顺序。在服务所定义的模型下,至多一次投递允许消息丢失,但避免重复的投递尝试。至少一次投递则允许重试和重复消息。声称具备恰好一次语义时,必须说明保证的范围:消息代理的状态、事务性的流处理操作,以及外部业务效果,分别属于不同的保证边界。将消息确认与数据库事务协调起来,可以解决某些故障情形;但如果还要向一个独立的外部系统写入数据,就会引入另一个一致性问题,除非有适当的协议将这些操作的效果关联起来。

分布式环境中的顺序保证同样有其范围。服务可能只在单个分区、单个生产者的消息流或单个消费者会话内保持顺序,而不是在所有消息之间保持顺序。重新投递和并行消费者还可能使首次投递顺序与处理顺序、完成顺序进一步分离。有些消息代理接口还支持优先级、延迟可用或过期机制,每一种机制都会改变其与简单先进先出序列之间的关系。抽象队列仍然是一个有用的基础,但不能仅凭“队列”一词就推断出可靠性和全局顺序保证。

库接口、不变量与验证

程序库通过抽象接口与具体容器的不同组合来提供队列功能。在 Java 中,Queue 定义了 add 与 offer、remove 与 poll 等成对方法,每对方法采用不同的失败报告方式;这一接口也允许选择规则并非先进先出的实现,例如 PriorityQueue。ArrayDeque 则可用于实现普通的先进先出行为。在 C++ 中,std::queue 是一个容器适配器,在底层容器之上提供受限的接口,默认底层容器为 std::deque。这些设计将一组操作与具体的存储表示分离开来。

Python 还作了另一种实用的区分。collections.deque 支持在两端进行高效操作,可以实现本地的先进先出队列;而 queue.Queue 提供生产者与消费者之间的协调操作、可选的容量上限以及任务计数机制。相比之下,Python 列表的 pop(0) 会移动后续元素,因此具有线性开销。在 JavaScript 中,push 和 shift 可以表达先进先出行为,但算法不应假定所有实现从头部移除元素的开销都是常数。采用环形表示或专用队列,可以避免依赖这种未明确承诺的性能保证。

验证从表示不变量入手。对于基于计数的循环缓冲区,典型条件包括 0≤n≤C0\leq n\leq C、队首索引位于数组边界内,以及逻辑位置 ii 到物理位置 (h+i) mod C(h+i)\bmod C 的映射。对于链式队列,两端引用必须与队列是否为空保持一致,队尾引用必须指向可达的最后一个节点,且该节点的后继链接必须为空。循环不变量可以用来证明,即使旧数组中的数据发生回绕,调整容量时的复制操作仍能保持序列不变。

一种实用的测试方法是生成操作历史,并以简单的序列模型为参照来检查实现。测试应覆盖空队列上的移除操作、重复值、空队列与单元素队列之间的状态转换、回绕、容量耗尽,以及数据处于回绕状态时的容量调整。使用需要区分对象身份的元素,可以发现仅比较值的测试可能遗漏的意外重复或丢失。对于有界覆盖式缓冲区,模型必须包含淘汰语义,而不能错误地将每次插入都视为不会丢失数据的操作。

并发验证需要考察操作历史,而不只是最终内容。测试可以记录操作调用、响应和返回值,再检查是否存在某个合法的顺序先进先出操作历史,满足实时先后顺序的约束。形式验证则可以将实现状态与抽象队列关联起来,并证明状态转换保持了所要求的行为。这些证明可能涉及原子操作、内存可见性、内存回收以及进展假设。通过顺序操作次序测试的队列,在操作相互重叠时仍可能出错;即使队列具有可线性化性,也仍可能违反另行规定的容量、取消或进展方面的契约。