栈

先处理最近留下的任务 ​

读到一对嵌套括号的右半边时，应该先结束哪一层？答案是最近开启、尚未结束的那一层。栈把这种规则变成一个接口：元素只从同一端进入和离开，最后放入的元素最先取出，称为后进先出（LIFO）。这一端叫栈顶，另一端叫栈底。

栈是一种抽象数据类型理路抽象数据类型Abstract data type · ADT由值集合与操作语义定义、独立于具体表示的数据接口。：它规定允许怎样操作、操作返回什么，不规定元素怎样存放。动态数组理路动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。和链表理路链表Linked list通过节点引用保存序列的存储结构；明确前驱、尾指针、节点身份与局部插删的复杂度条件。都能实现栈，但扩容、节点分配以及内存布局属于实现层。[1][2]

括号匹配为什么只需看栈顶 ​

扫描括号串时，栈保存已经遇到、还没有匹配的左括号，按开启次序排列。遇到左括号就压入；遇到右括号，它只能关闭栈顶对应的那一层。因此必须同时检查“栈非空”和“括号类型相同”，检查通过才弹出。

对于 ([)]，读到 ) 时栈底到栈顶依次为 (、[，栈顶是 [，所以立即判定不匹配。左右括号数量相等并不能保证结构正确；错误恰好发生在跨层关闭。对于 ([])，两个右括号依次关闭 [ 和 (，最后栈空，才说明所有层都已结束。

def brackets_match(text: str) -> bool:
    """检查三类括号；忽略其他字符。"""
    stack: list[str] = []
    partner = {')': '(', ']': '[', '}': '{'}
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in partner:
            if not stack or stack.pop() != partner[ch]:
                return False
    return not stack

算法的不变量是：每次扫描后，栈中恰好是当前前缀尚未关闭的左括号。左括号保持这一事实，合法右括号删除最近的一项；遇到失配时，任何后续字符也不能补救已经发生的交叉。长度为 $n$ 的文本只扫描一次，时间为 $O(n)$；空间为最大嵌套深度，最坏为 $O(n)$。

相同接口，成本保证可以不同 ​

以下成本以顺序 RAM 模型、常数大小元素和常数成本的局部内存操作为前提；链式实现还把单个节点的分配、释放按常数成本计算。

动态数组翻倍扩容时，连续压入 $n$ 个元素所产生的复制量受几何和控制：$1+2+4+\cdots <2n$。加上每次写入新元素的成本，总时间仍是 $O(n)$。这说明平均分摊到每次操作为常数，并没有让触发扩容的那一次操作变成常数时间。若允许缩容，通常在占用降到容量四分之一时才减半，避免在容量边界反复复制。[1]

使用双端队列理路双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。时，只使用同一端的一组操作，也能实现栈接口。但若把“删除任意中间元素”暴露给客户端，提供的就是比纯栈更强的接口；这与内部偶尔移动元素是两回事。

栈怎样组织算法的控制流 ​

函数调用形成嵌套关系时，调用栈保存尚未完成的活动记录，其中可以包含返回位置、局部变量等信息。内层调用结束后，恢复最近暂停的外层调用，正好符合 LIFO。具体运行时可能优化尾调用，所以不应把每个源代码层面的调用都机械等同于新增一个物理栈帧。

深度优先搜索理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。使用栈保存待继续探索的分支。递归写法让运行时维护这份状态；显式写法把它放进程序可管理的栈。若要精确复现递归访问次序，还需保存当前邻接表位置，或相应调整邻居的压栈顺序。

单调栈理路单调栈Monotonic stack用右侧首个严格更大元素串起索引不变量、逐步轨迹、可运行代码与摊还证明，并区分结算和支配两类弹栈理由。则在普通 LIFO 之上增加一个不变量：栈内元素按某种大小关系排列。新元素到来时，持续弹出已经失去候选资格的元素。线性时间通常来自每个元素至多入栈、出栈各一次，而不是因为一轮循环只能弹出一次。

与队列理路队列Queue · FIFO queue在队尾加入、从队首取出，并保持尚未离队元素的到达次序的抽象数据类型；循环数组和链表给出不同表示。的先进先出规则相比，栈优先处理最近加入的元素。