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

栈(数据类型)

栈是一种按后进先出顺序存储元素的抽象数据类型,支持在指定的一端插入和移除元素。

37 个关键词23 个词条链接到这里12 个尚未撰写AI 撰写
抽象数据类型计算机科学数据结构形式验证链表摊还分析CPU缓存时间复杂度栈(数据类…

栈是一种抽象数据类型,元素的添加和移除都在指定的一端进行,这一端称为栈顶。栈的核心规则是后进先出(LIFO):在仍留在栈中的元素里,最后插入的元素最先被移除。栈的主要操作是入栈(push)和出栈(pop),前者添加一个元素,后者移除栈顶元素。查看栈顶(peek 或 top)操作则读取栈顶元素,而不将其移除。

栈是计算机科学中的基础概念,因为它能直接表示嵌套活动。它可以记录尚未完成的函数调用、表达式求值中等待处理的运算符、之后可能撤销的选择,以及求解问题时尚未探索完的路径。栈可以用多种不同的数据结构来实现;决定它是否为栈的是其可观察到的行为,而不是某种特定的内存布局。抽象的栈还应与程序的运行时栈区分开来,后者是栈式存储的一种重要应用。

定义、操作与行为契约

栈可以建模为一个有限序列 S=⟨x1,x2,…,xn⟩S=\langle x_1,x_2,\ldots,x_n\rangle,其中的元素按从栈底到栈顶的顺序排列。元素 xnx_n 位于栈顶,空栈表示为 ⟨⟩\langle\rangle。如果用 S∥⟨x⟩S\mathbin{\|}\langle x\rangle 表示在序列末尾追加 xx,那么将 xx 入栈的结果为

push⁡(S,x)=S∥⟨x⟩.\operatorname{push}(S,x)=S\mathbin{\|}\langle x\rangle.

对于非空栈,出栈操作同时返回最后一个元素和剩余序列:

pop⁡(⟨x1,…,xn⟩)=(xn,⟨x1,…,xn−1⟩).\operatorname{pop}(\langle x_1,\ldots,x_n\rangle) = \bigl(x_n,\langle x_1,\ldots,x_{n-1}\rangle\bigr).

这种数学记法描述的是状态转换;编程接口也可以改为修改现有对象,并仅返回被移除的值。

栈的核心行为规律是:将一个元素入栈后立即出栈,会返回该元素,并使栈恢复到入栈前的状态。例如,依次将 A、B 和 C 入栈,再执行三次出栈操作,返回的结果依次为 C、B 和 A。这里的顺序针对的是插入操作的发生次序,而不是不同的值:将两个相等的值入栈,会创建两个独立的条目。栈通常还提供 isEmpty、size 和 clear 操作。有界栈还可能提供查询容量或判断栈是否已满的操作。这些辅助操作都不会改变后进先出规则。

出栈和查看栈顶元素的操作都需要规定空栈情况下的处理策略。接口可以抛出异常、返回可选值、通过布尔结果报告失败,或者将栈非空设为前置条件。只有在不会与有效元素混淆的情况下,才能使用特殊的哨兵值。在没有元素时尝试移除元素,称为栈下溢。栈溢出可以指超出有界栈的容量;在运行时系统中,同一术语通常指函数调用所需的存储空间耗尽。这些情况采用了相同的存储比喻,但其成因和处理机制未必相同。

抽象契约并不规定内存分配策略、线程安全性、元素所有权,也不规定出栈操作是否返回值。例如,C++ 的标准栈适配器将通过 top() 查看栈顶元素与通过 pop() 移除元素分为两个操作,而许多其他接口则将获取与移除合并为一个操作。同样,实现可以提供迭代或按索引查看元素的功能,同时仍然提供栈操作,不过任意移除元素不属于最基本的栈抽象。区分契约与这些扩展功能,对于形式验证十分重要:正确性意味着,无论内部如何表示元素,每个允许执行的操作都必须产生抽象规范所规定的结果。

表示方式、不变式与复杂度

两种标准的表示方式是连续数组和链表。在容量为 CC 的数组表示中,用整数 nn 记录已占用位置的数量,有效元素占据从 00 到 n−1n-1 的位置。栈顶位于位置 n−1n-1。入栈时,将元素写入位置 nn,并将计数加一;出栈时,将计数减一,并取出由此显露的位置上的元素。基本的表示不变式是 0≤n≤C0\leq n\leq C,以及数组已占用的前缀部分与抽象序列之间的对应关系。

对于容量固定的数组,在通常的单位成本模型下,假设存储空间已分配,且元素操作本身的成本为常数,则入栈、出栈和查看栈顶元素都需要 O(1)O(1) 时间。动态扩容数组通过在必要时分配更大的缓冲区,消除了固定容量的限制。一次扩容可能需要复制或移动全部 nn 个元素,耗时 O(n)O(n),但按几何级数增长容量可使入栈的摊还时间达到 O(1)O(1)。若每次将容量翻倍,连续各次扩容所移动的元素数量便构成一个几何级数,因此 mm 次入栈操作中的元素搬移总工作量为 O(m)O(m)。这是摊还分析的应用,并不保证每一次入栈都很快。

缩容同样需要谨慎处理。如果缓冲区在满时扩容,又在刚有一半空间空闲时立即将容量减半,那么在临界点附近交替入栈和出栈,就可能反复触发大规模复制。采用彼此分离的阈值可以避免这种情况,例如在满时将容量翻倍,在占用率降至四分之一时将容量减半。保留未使用的容量也可能是有意为之:这样可以减少内存分配活动,代价是保留一些当前并未被栈元素占用的内存。

链式表示存储一个栈顶指针,各节点包含一个元素和指向下一节点的链接。入栈时创建一个节点,使其后继指向原来的栈顶;出栈时,将栈顶指针移至其后继节点。这两种操作都不需要遍历。指针修改耗时为常数,但内存分配、释放以及内存管理引起的暂停未必如此。每个节点还需要一个链接字段,并且可能带来分配器元数据和内存对齐方面的开销。与数组不同,节点不必彼此相邻,因此其 CPU 缓存局部性通常较差。单独维护一个元素计数,可以使大小查询在常数时间内完成;否则,就需要遍历链表来统计节点数。

因此,表示方式影响的不只是渐近时间复杂度。数组有利于局部性和紧凑存储,链式节点避免了整个缓冲区的搬移,而分段栈则将固定大小的块与增量扩容结合起来。实际成本还取决于栈存储的是值还是引用、复制元素是否代价高昂,以及移除条目时是否必须销毁对象。在采用垃圾回收的实现中,清空不再使用的数组槽位,可以避免本应已不可达的对象仍被保留。严谨的比较应明确具体操作、成本模型、最坏情况或摊还界,以及相关的内存开销,而不是笼统地将所有栈都描述为“常数时间”。

搜索、嵌套与可逆计算

当算法必须先完成最近开始的任务,才能返回先前的任务时,栈尤其有用。括号匹配检查就是一个直接的例子。遇到左圆括号、左方括号或左花括号时,算法将其类型或位置入栈。遇到右括号时,算法先检查栈是否非空,以及栈顶的左括号是否与之匹配,然后将其出栈。出现多余的右括号或括号类型不匹配,就表示检查失败;输入结束后,如果栈仍非空,则表示还有未匹配的左括号。对于长度为 nn 的输入,该过程的时间复杂度为 O(n)O(n),辅助空间复杂度为 O(d)O(d),其中 dd 为最大嵌套深度。

深度优先搜索采用同样的“最近开始的任务优先”规则来探索图。递归式深度优先搜索通过函数调用实现栈的行为。迭代版本则显式存储顶点、边或暂停的探索状态。要精确复现递归版本发现和完成各顶点的顺序,每个显式栈帧可能都需要同时记录一个顶点及其下一个待检查的邻接顶点。在采用适当标记规则的情况下,仅将每个邻接顶点压入栈,也能得到有效的深度优先式探索,但未必能复现某次递归遍历的所有细节。当算法依赖完成时间、父子关系或边的分类时,这一区别就很重要。

相应的空间复杂度取决于存储的内容。如果每个栈帧只记录当前路径及局部处理进度,那么遍历一棵树可以使用 O(h)O(h) 个栈帧,其中 hh 为树高。一般的图遍历通常还需要一个记录已访问顶点的数据结构,以避免沿环反复探索。因此,即使当前活动路径很短,其辅助存储总量也可能达到 O(V)O(V)。广度优先搜索按到达顺序安排待处理任务,而深度优先搜索则先沿着最近发现的分支继续探索,再返回较早发现的其他分支。

回溯在此基础上增加了对试探性决策的撤销。解谜程序可以将某个选择及恢复先前状态所需的信息压入栈,探索这一选择的后果,并在放弃该分支时将这些信息弹出。撤销系统也采用类似模式,用栈存储命令、逆操作、快照或状态之间的差异。常规的撤销与重做界面使用两个栈:撤销将一个操作从撤销栈移到重做栈,重做则将其移回。撤销后再进行新的编辑,通常会清空重做历史,因为原先的后续操作已不再是当前状态的延续。

另一类重要的栈是单调栈,其元素始终保持递增或递减顺序。要为数组中的每个元素找到其右侧下一个更大的值,算法可以从左向右扫描,并将尚未找到答案的元素下标保存在栈中。遇到一个新值时,先为栈中比它小的值确定答案,并将对应下标弹出,然后再将新值的下标压入栈。虽然一次迭代可能弹出许多元素,但每个下标只入栈一次,至多出栈一次,因此总时间复杂度为 O(n)O(n)。这一技巧可用于直方图面积算法、股票跨度计算,以及多种查找最近较大或较小元素的查询。

表达式处理与栈机

表达式求值简明地展示了栈如何将语法上的嵌套转化为计算。在后缀表示法中,运算符位于操作数之后,因此 3 4 + 2 * 表示 (3+4)×2(3+4)\times2。求值器从左到右扫描词元,将每个操作数压入栈中。读到二元运算符时,先弹出右操作数,再弹出左操作数,执行运算,然后将结果压入栈中。对于减法和除法,操作数的顺序至关重要:词元序列 8 2 / 必须计算 8/28/2,而不是 2/82/8。

对于由操作数和二元运算符组成的合法表达式,求值结束时栈中恰好剩下一个值。遇到运算符时,如果栈中可用的值不足两个,就表明存在错误;如果最后剩下多个值,则说明该词元序列未将所有操作数合并为一个结果。更通用的求值器还会处理一元运算符、参数个数固定或可变的函数、类型以及运行时错误。如果词元处理和单次运算的成本都有固定上界,求值的时间复杂度就与词元数量成线性关系。对于任意精度算术或用户自定义运算,则需要更细致的成本模型。

中缀表达式需要一套处理括号和运算符优先级的方法。艾兹格·戴克斯特拉于 20 世纪 60 年代初提出的调度场算法使用一个运算符栈和一个输出序列。读入一个运算符时,算法会依据优先级和结合性,将栈中相应的待处理运算符弹出。左括号用于划定边界;遇到右括号时,则不断弹出运算符,直到对应的左括号。对于左结合的减法,a - b - c 按 (a−b)−c(a-b)-c 分组;对于右结合的乘方运算符,遇到优先级相同的运算符时,则需要采用不同的处理方式。该算法可以生成后缀表示,也可以经过改造来构建表达式树。

栈也是编译器中自底向上语法分析的基础。LR 分析器维护一个分析器状态栈,栈中通常还同时保存文法符号或语义值。移进操作消耗一个输入词元,并将下一个状态压入栈中。归约操作识别某条文法产生式的右部,移除对应的栈项,再压入一个由归约所得非终结符决定的状态。这比定界符匹配具有更严密的结构:分析栈以压缩形式记录了决定后续动作所需的语法上下文。文法歧义和语法分析冲突仍然是文法与分析方法本身的性质,并不是仅靠选用栈就能解决的问题。

栈机将这种求值模型扩展为一种执行架构。指令从操作数栈中隐式取得操作数,并将结果留在栈中,从而减少了在每条指令中编码寄存器名称的需求。Java 虚拟机为每次方法调用分配一个操作数栈,作为其栈帧的一部分;其他字节码系统也采用面向栈的执行模型。操作数栈与调用栈在概念上有所区别:前者保存计算过程中的中间值,后者记录尚未结束的调用。具体实现可以将这两种抽象中的任何一种优化为寄存器或其他存储形式,同时保持规范所规定的可观察行为不变。

运行时调用栈与控制流

调用栈记录当前尚未结束的函数或过程调用。当一个函数调用另一个函数时,执行流程通常会先进入被调用函数,调用方则要等到被调用函数返回后才能继续执行。这自然遵循后进先出的顺序。每次尚未结束的调用通常用一个栈帧(也称活动记录)来表示,其中包含返回信息、局部变量、保存的寄存器、参数以及管理信息等内容的某种组合。具体内容及其布局取决于编译器、优化设置、处理器架构和应用二进制接口。

栈指针标识当前使用的栈存储区域的一个边界。有些系统还使用帧指针,以便稳定地访问栈帧中的内容,不过经过优化的代码可能会省略帧指针。许多处理器的约定使栈向低内存地址方向增长,但向下增长并不是栈的抽象定义的一部分。也并非每次调用都必须分配常规的内存栈帧:叶函数可以将全部工作状态保存在寄存器中,内联会完全消除调用边界,而某些调用约定会将返回地址保存在寄存器中,直到必须保存该值时才将其转存到别处。

递归要求为同时处于活动状态的各次调用分别保存状态。如果某个函数递归处理一条深度为 dd 的链,且每次调用所需的存储空间有固定上界,那么它对调用栈空间的需求通常为 O(d)O(d)。递归遍历平衡二叉树时,最大深度可能是对数级的;而遍历退化树时,深度可能是线性级的。将递归转换为迭代,往往只是将同样的待处理状态转移到显式栈中,而非将其消除。反过来,如果语言及其实现允许消除尾调用,那么尾调用就可以通过复用当前栈帧来实现。

非局部控制流使简单的调用与返回模型变得复杂。异常可能需要展开多个栈帧,才能到达处理程序;在栈展开过程中,语言运行时可能会执行清理操作并销毁局部对象。调试器和性能分析器会利用栈帧信息、栈展开元数据或其他实现特有的机制,还原当前尚未结束的调用。协程可以挂起一次调用,并在稍后恢复,因此其状态可能保存在独立的栈中,也可能保存在堆上分配的状态对象中。这些实现能够保持所需的控制流语义,而不要求所有已挂起的任务都占用同一个普通的连续调用栈。

运行时栈空间耗尽与缓冲区溢出并不是一回事。前者发生在程序执行所需的栈存储空间超过可用空间时,常见原因是递归层次过深或分配的栈帧过大。后者发生在程序访问超出缓冲区边界时,可能破坏相邻内存;如果缓冲区位于栈帧中,被破坏的内容还可能包括控制数据。保护页有助于检测栈空间耗尽,而边界检查、栈金丝雀和控制流保护则分别应对内存破坏的不同方面。普通的栈容器对象也可以分配在动态管理的内存中;将某个容器称为栈,并不意味着它的元素位于线程的运行时栈上。

接口、所有权与可持久化版本

栈的应用程序编程接口决定了其抽象行为如何与语言的类型系统和内存模型相契合。可变接口会原地修改同一个栈对象;不可变接口则返回一个新的栈值,旧值仍可继续使用。两者都能满足后进先出语义。不同接口还存在其他差异,例如是否暴露元素的引用、是否允许迭代、是否接受最大容量参数,以及是否将操作失败与存储的空值区分开来。这些选择虽然不会改变底层的元素次序规则,却会影响安全性和易用性。

标准库体现了这些差异。C++ 提供了容器适配器 std::stack,其默认底层容器是 std::deque;也可以使用其他兼容的容器提供存储。它的 top() 用于查看栈顶元素,而 pop() 只移除栈顶元素,不返回该元素。Java 保留了较早的 Stack 类,但其集合文档建议在需要后进先出行为时使用 Deque 的实现,ArrayDeque 就是一个常见例子。在 Python 中,列表通过在右端调用 append() 和 pop() 来支持常规的栈操作。在 JavaScript 中,数组提供了类似的 push() 和 pop() 方法。这些用途更广的容器还提供了最小栈抽象之外的操作。

当元素负责管理资源,或者 API 返回指向内部存储的引用时,所有权就变得十分重要。数组在增长时可能会迁移元素,使先前指向这些元素的指针或引用失效。移除元素意味着该元素不再属于栈,但这对底层对象产生何种影响,取决于栈是直接存储该对象、间接拥有该对象,还是仅持有一个共享引用。入栈失败时的行为也需要明确定义:如果内存分配或元素构造失败,实现可以保证原有的栈保持不变。这类保证不仅涉及异常的报告,也涉及可观察的状态。

不可变链式栈是可持久化数据结构的一个简单例子。如果用一个包含值和指向剩余部分的引用的节点来表示栈,那么入栈操作只需创建一个指向旧栈的新节点。出栈操作则返回引用所指向的剩余部分,而不修改任何链接。因此,栈的多个版本可以共享大部分存储。例如,在同一个旧栈上分别将 A 和 B 入栈而创建的两个栈,其栈顶节点不同,但共享此前的整个序列。

这种表示方式在函数式编程中很常见,因为不可变列表天然支持在常数时间内访问表头和表尾。只有不对共享节点进行破坏性修改,共享才是安全的。共享也改变了空间用量的计算方式:从一个版本中移除元素后,如果另一个仍可达的版本还引用着该元素,就不能回收它。垃圾回收、引用计数或其他生命周期管理机制必须将所有仍存续的版本都考虑在内。因此,可持久化栈的入栈和出栈具有常数时间复杂度,指的是局部结构操作,并不意味着内存分配造成的停顿、回收工作量或应用程序保留的内存总量也有无条件的上界。

并发栈与同步

当多个线程共享一个栈时,要保持后进先出的行为,就需要规定如何处理执行时间重叠的操作。一种常见的正确性条件是线性一致性:每个操作都必须表现为在其调用与完成之间的某一瞬间生效,而且由此形成的顺序必须符合互不重叠操作的实际时间顺序。如果两次入栈操作的执行时间重叠,任何一个都可以排在前面。如果一次入栈操作在另一次开始之前就已完成,那么后续的出栈操作必须遵循这一既定顺序,除非中间已有操作移除了相关元素。

基于锁的实现通过互斥来保护栈的状态。入栈、出栈或复合操作会进入临界区,更新或检查共享的数据表示,然后释放锁。正确划定临界区的边界至关重要。分别对 isEmpty() 和 pop() 调用进行同步,并不能使“检查非空,然后出栈”这一组合成为原子操作:另一个线程可能在这两次调用之间移除最后一个元素。将尝试移除元素与报告失败合并为一个操作的接口,可以避免这一特定的竞态条件。阻塞栈还会加入协调机制,使消费者能够等待元素到来,而不必反复检查。

一种得到广泛研究的非阻塞实现是 R. Kent Treiber 于 1986 年描述的链式栈。入栈操作先读取当前栈顶指针,让新节点指向它,再使用比较并交换,仅在栈顶指针仍为预期值时将其替换。出栈操作同样先读取栈顶及其后继节点,然后尝试将栈顶指针替换为指向该后继节点的指针。如果其他操作的干扰导致比较失败,该操作就会根据新的状态重试。只要正确处理节点发布、内存序和节点生命周期,成功的原子更新就提供了一个自然的线性化点。

内存回收是其中的核心难点之一。一个线程可能刚读到某个指针,另一个线程就移除并释放了对应的节点。复用这块存储空间还可能引发 ABA 问题:指针的值从 A 变为 B,随后又变回 A,导致比较操作无法察觉中间发生的变化。带标签指针可以帮助区分不同版本,但仅有版本标签并不能保证解引用节点是安全的。危险指针、基于纪元的内存回收以及合适的垃圾回收环境,在不同假设下解决了这一生命周期问题的不同方面。这些机制是保证正确性不可或缺的组成部分,而不是可有可无的性能优化。

非阻塞的进展保证也不同于操作顺序的正确性。无锁算法在其规定的执行假设下保证系统整体持续取得进展,但单个操作可能在竞争中反复失败。无等待算法则保证每个操作只需执行有界数量的自身步骤。这两个术语都不意味着竞争没有代价。在并行计算中,单个共享栈顶指针可能成为缓存一致性瓶颈。消除技术允许执行时间重叠的入栈和出栈操作直接交换值,而不必访问这个中心指针,同时仍能保持有效的抽象操作顺序。这类技术的收益取决于工作负载的均衡程度、竞争程度、调度方式以及配套的内存管理方案。

历史发展与理论基础

栈的思想源于临时存储、表达式翻译以及子程序返回等实际需求。20 世纪 50 年代,弗里德里希·L. 鲍尔和克劳斯·萨梅尔森提出了颇具影响力的基于栈的公式翻译方法。同一时期,查尔斯·汉布林独立推动了面向栈的表达式求值和后缀记法的发展。这些进展将一种简单的存储规则与嵌套算术表达式的自动化处理联系起来,推动栈成为编程语言实现中的基本工具,而不再仅仅是一种专门的内存组织方式。

随后,面向栈的硬件和语言使这一抽象概念更加广为人知。1961 年推出的 Burroughs B5000 是一款颇具影响力的早期商用计算机,采用面向栈的体系结构,专为高级语言的执行而设计。查尔斯·H. 摩尔开发的 Forth 语言将显式的数据栈置于编程的核心位置,同时还使用了一个独立的返回栈。后来的字节码系统采用面向栈的指令格式,以实现可移植的执行。这些系统在表示方式和指令设计上差异很大,但都利用了栈的一项特性:能够隐式引用最近产生的值或最近建立的控制上下文。

在计算理论中,下推自动机是一种增设了栈的有限状态机。它的转移规则可以检查当前状态、输入符号(如适用)以及栈顶符号,然后改变状态,并用一个有限的符号序列替换栈顶符号。栈提供了潜在无界的存储空间,同时将访问限制在一端。这足以识别普通有限状态机无法识别的嵌套模式,例如任意深度的配对括号,或语言 {anbn∣n≥0}\{a^n b^n\mid n\geq0\}。

非确定性下推自动机所能识别的语言恰好就是上下文无关语言,这构成了文法与机器之间的一项基础性联系。确定性下推自动机所能识别的语言则是这类语言的一个真子集。这一区别对语法分析很重要:一种语言存在上下文无关文法,并不意味着任何确定性语法分析策略都能不加限制或变换地直接处理该文法。理论上的栈通常是无界的,而物理实现的容量则是有限的;理论结果讨论的是模型的能力,并不是断言实际内存具有无限容量。

两个无界栈会显著改变计算能力。一个栈可以表示模拟读写头左侧的纸带,另一个栈则表示当前单元及其右侧的纸带;随着读写头移动,符号在两个栈之间转移。配合适当的有限状态控制机制,这就具备了图灵机的计算能力。这一对比明确揭示了单栈访问方式的局限,而不仅仅是存储容量的局限。在模型中,单个栈可以容纳任意多个符号,但其受限的访问顺序仍然制约着机器能够识别的语言。访问规则、嵌套结构与计算能力之间的这种关系,也是栈在实际执行系统和形式语言理论中始终占据核心地位的原因之一。