栈Stack

按后进先出顺序保存与取出元素。

入栈和出栈都操作栈顶。当前 pop 得到 C；若先 push D，下一次 pop 得到 D。

常见操作#

n 为栈内元素数。

操作	时间复杂度	条件与说明
查看栈顶	$O(1)$	只读最后入栈的元素，不移除。
压栈	摊还 $O(1)$ ；扩容最坏 $O(n)$	动态数组实现；链式实现更新栈顶为 $O(1)$ ，分配成本另计。
弹栈	$O(1)$	不触发缩容的数组栈或链式栈；带缩容的数组栈按摊还分析。
遍历 / 查找任意元素	$O(n)$	最坏访问全部元素；这些操作不属于栈的核心接口。

动态数组和链表都可实现栈，但扩容、分配和局部性不同。

2 个案例 · 附源码

Linux Kernel·BPF verifier / 控制流图检查v6.12

Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。

附源码片段 · 图处理与编译

LLVM·Legacy CallGraphSCCPassllvmorg-19.1.0

LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。

附源码片段 · 图处理与编译

基础原理参考资料

Princeton · ResizingArrayStack动态数组栈的压栈、弹栈与摊还保证。

Princeton · Stack链式栈的常数时间接口。