栈

栈把所有更新集中在顶部这一端，保持后进先出：最后进入的元素最先离开。它把尚未完成的嵌套任务按进入顺序压入，最近开启者最先收束，因此与递归调用、括号匹配和深度优先遍历天然同构。栈的关键是这种可观察顺序，而不是使用数组还是链表；数组实现只需一个顶部索引，链式实现则在表头插删。

括号匹配时，遇左括号压栈，遇右括号检查并弹出最近未匹配的左括号。调用栈记录嵌套函数活动。若允许从中间任意删除，就不再是纯栈接口。

扫描括号串 ([]) 时，遇到左括号依次压栈，右括号必须与栈顶类型匹配并弹出，最终栈空才合法。表达式求值中，运算符栈保存尚待结合的操作，优先级决定何时弹出。

栈下溢表示对空栈 pop，必须定义错误行为；固定数组还可能上溢。调用栈保存的不只是返回地址，还可能含局部变量和异常处理信息，深递归会耗尽系统栈；显式栈可以控制内存与遍历顺序。

深度优先搜索公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。、表达式求值、语法解析和回溯依赖 LIFO 次序；双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。只使用同一端时可实现这组操作。顺序 RAM 中，动态数组或链表可给 push、pop、top 的摊还或最坏 $O(1)$，具体保证取决于表示，不属于栈 ADT 本身。

单调栈可在线性扫描中为每个元素寻找支配边界，Cartesian Tree公理库笛卡尔树Cartesian tree同时满足下标中序与数组值堆序的唯一二叉树。把这组弹栈关系固化为同时满足中序与堆序的树。平衡括号树表示公理库平衡括号树表示balanced-parentheses tree representation · BP tree encoding用 DFS 的进入/退出括号串以 2n 位编码有序根树，并把父子、兄弟和子树查询化为 matching 与 excess 搜索。则利用 DFS 的入栈/出栈生成括号序列，再在该序列上支持导航。若要共享尾部并保留历史版本，应使用持久化数据结构公理库持久化数据结构Persistent data structure · Persistence in data structures更新产生新版本而保留旧版本可访问性，并通过结构共享控制时间与空间的数据结构技术。的版本语义，而不是把普通数组栈直接称为持久化。