栈

栈最先暴露最近压入的元素，即后进先出。最小操作集包括 push、pop、peek 和判空。

stack: list[str] = []
stack.append("first")
stack.append("second")
top = stack[-1]
removed = stack.pop()

使用动态数组末端时，压入和弹出的摊销成本为 $O(1)$，查看栈顶为 $O(1)$。链式实现可以保证端点更新最坏为 $O(1)$，但每个元素都要多一次分配和一条链接。

不变量

只有栈顶可以直接移除。这种访问限制表达了尚未完成的工作：栈顶通常代表最近打开的分隔符、当前搜索状态、待处理运算符或可撤销操作。

常见用途

• 迭代式深度优先搜索和回溯；
• 表达式解析和分隔符匹配；
• 撤销历史和嵌套作用域；
• 需要显式控制状态时模拟递归。

语言运行时调用栈与此相关，但还会保存返回地址、局部变量和执行元数据；它不只是用户层面的值栈。

失效与容量

从空栈弹出属于下溢，接口应明确规定其行为。有界栈也可能溢出；动态实现面对的则是内存分配失败或策略限制。

不要用动态数组的前端插入和删除模拟栈，这会引入不必要的元素移动。

示例：检查嵌套分隔符

def balanced(text: str) -> bool:
    opening: list[str] = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in text:
        if char in "([{":
            opening.append(char)
        elif char in pairs:
            if not opening or opening.pop() != pairs[char]:
                return False
    return not opening

assert balanced("a * (b + [c])")
assert balanced("")
assert not balanced("([)]")
assert not balanced(")(")
assert not balanced("((")

每接受一个字符后，栈中恰好按出现顺序保存尚未匹配的左分隔符。右分隔符必须匹配栈顶，不能只在前面找到任意一个同类左分隔符：([)] 的数量相等，但嵌套关系交叉了。遍历结束时栈为空，才说明没有尚未闭合的左分隔符。对于 $n$ 个字符，时间成本为 $O(n)$；若最大嵌套深度为 $d$，额外空间为 $O(d)$。

这个函数只检查分隔符嵌套。它忽略其他字符，却不理解引号内的字符串或注释，因此不是编程语言解析器。页面开头的示例中，top 和 removed 都是 "second"，剩下的栈为 ["first"]。对空 Python 列表执行 stack[-1] 或 stack.pop() 都会抛出 IndexError。

采用合理的扩缩容策略时，动态数组的弹出操作可以保证摊销 $O(1)$，不能一概称为最坏 $O(1)$；查看栈顶仍为 $O(1)$。链式端点的成本计算链接修改次数，不保证实际内存分配耗时恒定。

来源

• Open Data Structures：栈接口

我的阅读 · 打开过的笔记会记在当前浏览器里。