tech-interview-handbook 中的栈（Stack）面试指南：从 LIFO 原理、复杂度分析到单调栈技巧

本文基于 tech-interview-handbook 仓库中的 stack.md 栈专题速查表展开，系统讲解栈的抽象数据模型、各语言标准库 API、时间复杂度、边界情况，以及面试中必练的经典栈题与单调栈技巧。读完后，你将能够独立选择合适的栈实现、按复杂度表口述关键操作的 Big-O、识别空栈等边界情况，并掌握从 Valid Parentheses 到 Trapping Rain Water 的完整刷题路径。

1. 什么是栈：LIFO 模型与两种底层实现

栈（Stack）是一种抽象数据类型（ADT），只支持两个核心操作：

• push：在栈顶插入一个新元素；
• pop：移除并返回最近添加的元素（即栈顶元素）。

这种"后进先出"（LIFO, Last In First Out）的行为，正是"stack"这个名称的由来——它类比现实生活中一摞物品上下叠放的场景：最上面放的最后取，最先放的最后取。

作为抽象数据类型，栈可以用数组或单向链表来实现。这一点在原文档中明确给出（"stacks can be implemented using arrays or singly linked lists"）。两者的取舍大致是：

• 数组实现（如 Python list、JavaScript Array）：push/pop 发生在尾部时均为均摊 O(1)，内存连续、缓存友好，是最常用的面试实现；
• 链表实现：头部插入/删除恒定 O(1)，无需扩容，但节点对象分散在堆上，常数因子更大。

栈在编程中有两个关键用途，原文档点出了其中的重点：

1. 支撑嵌套或递归函数调用：语言运行时用调用栈（call stack）保存每层函数的局部变量、返回地址，递归本质上就是显式地在栈上"压入"一层执行上下文、再"弹出"返回；
2. 实现深度优先搜索（DFS）：DFS 既可以用递归（隐式使用调用栈），也可以用手动维护的显式栈（manual stack）来实现。

在仓库中可以直接看到"显式栈"的真实用法：tree_traversal.py 用 stack = [root] 配合 stack.pop() / stack.append() 完成了非递归的前序遍历——先 pop 出当前节点处理，再先把右子节点、后把左子节点压栈，利用 LIFO 保证左子树先被访问。这正是"用数组模拟栈"在面试代码里的标准形态。

2. 各语言的标准库与替代实现

原文档给出的实现对照表如下（面试中建议直接口述这张表）：

语言	栈 API	说明
C++	std::stack	标准库容器适配器，默认底层为 std::deque
Java	java.util.Stack	官方栈类（继承自 Vector，面试中也可用 ArrayDeque 获得更好的性能）
Python	用 list 模拟	list.append() 等价 push，list.pop() 等价 pop，list[-1] 等价 peek
JavaScript	用 Array 模拟	arr.push() / arr.pop() / arr[arr.length - 1]

这里有一个值得在面试中主动说明的点：Python 和 JavaScript 没有内置的 Stack 类，候选者通常直接用 list/Array 模拟。与"用 list 模拟队列"不同（在 queue.md 中明确指出，list 模拟队列时从头部 dequeue 需要搬移全部元素，退化为 O(n)），用 list 模拟栈是完全安全的——因为 push/pop 都发生在列表尾部，不需要搬移其他元素，因此 O(1) 复杂度成立。

下面给出一个用 Python list 模拟栈的最小可用封装，可作为面试白板编码的起点：

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):        # O(1)
        self._items.append(item)

    def pop(self):               # O(1)，空栈需防御
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):               # O(1)，即 top
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]

    def is_empty(self):           # O(1)
        return len(self._items) == 0

注意 pop 和 peek 前都对空栈做了防御，这直接呼应原文档列出的第一个 corner case（见第 5 节）。

3. 时间复杂度速查表

原文档给出的复杂度表是面试口述的"标准答案"：

操作	Big-O	说明
Top/Peek	O(1)	只查看栈顶，不删除
Push	O(1)	尾部追加，数组实现为均摊 O(1)
Pop	O(1)	尾部弹出，数组实现为均摊 O(1)
isEmpty	O(1)	维护长度变量即可
Search	O(n)	栈不支持随机访问，查找必须逐个弹出或遍历

面试中的实际意义：

• 凡是算法的每个元素"进栈 + 出栈"各至多一次，则栈部分的总复杂度仍是 O(n)（例如用单调栈解 Daily Temperatures）；
• 如果解法需要频繁 Search（在栈中查找任意元素），O(n) 的搜索会把整体复杂度拉高，此时应改用哈希表等辅助结构——这与仓库 study-cheatsheet.md 中"数据结构可以被增强以在不同操作上获得高效时间复杂度"的通用建议一致。

4. 栈与 DFS：递归版与显式栈版

原文档指出："Depth-first search can be implemented using recursion or a manual stack." 仓库中提供了递归版 DFS 的参考实现 graph_dfs.py，其核心是一个内部 dfs(i, j) 递归函数，靠调用栈隐式保存访问状态：

def dfs(i, j):
    if (i, j) in visited:
        return
    visited.add((i, j))
    for direction in directions:
        next_i, next_j = i + direction[0], j + direction[1]
        if 0 <= next_i < rows and 0 <= next_j < cols:
            dfs(next_i, next_j)

将其改写为显式栈版本，模式是固定的——"把递归的一次调用变成一次 push，把函数返回变成一次 pop"：

def dfs_iterative(start):
    visited = set()
    stack = [start]                      # 手动栈
    while stack:
        node = stack.pop()                # 等价于递归进入一层
        if node in visited:
            continue
        visited.add(node)
        for neighbor in neighbors(node):
            stack.append(neighbor)      # 等价于发起递归调用

从源码结构看，仓库的 tree_traversal.py 中后序遍历的写法还展示了一个更精细的技巧：节点被压栈后先压左子树、再把节点重新压回栈并清空 left 指针，待节点"第二次出栈"时才收集结果——这体现了显式栈模拟"延迟执行"的一般手法：需要控制"访问时机"时，可以把节点连同状态多次入栈。

面试中建议主动给出这两种写法：递归版代码短，显式栈版在树深度接近 n（如退化为链的树）时可避免递归深度带来的栈溢出风险。

5. Corner cases：空栈、单元素栈、双元素栈

原文档明确要求覆盖三类边界情况，这也是每题写完后自测的固定清单：

• 空栈：对空栈执行 pop/peek 会抛异常（Python list.pop() 抛 IndexError，Java 抛 EmptyStackException）。面试中要么先判空，要么与面试官确认输入保证非空；
• 只有一个元素的栈：pop 之后栈变空，后续逻辑不能再假设"还能 pop 出一个配对元素"——Valid Parentheses 中 "]" 这类输入正是考察此处；
• 有两个元素的栈：连续两次 pop 的顺序是否真的是 LIFO；用栈模拟队列等题目中，双元素是检验"搬运方向"是否写反的最小用例。

这与仓库 study-cheatsheet.md 的通用建议一致："Always validate input first. Check for invalid/empty/negative/different type input."，且写完后"用几个示例输入测试你的解法"。

6. 必练题（Essential questions）

原文档将以下两题列为学习本主题时的必做题（题名为 LeetCode 题目，仓库以链接形式给出，此处按名称列出以便搜索）：

1. Valid Parentheses（有效的括号） 栈的经典入门题：遇到左括号入栈，遇到右括号时弹出栈顶并校验是否匹配；结束时栈必须为空。它同时覆盖三个 corner case：空串（合法）、] 开头的单元素非法输入、"()" 双元素合法输入。
2. Implement Queue using Stacks（用栈实现队列） 用两个栈模拟 FIFO：入队压入 inStack；出队时若 outStack 为空则把 inStack 全部倒序搬入 outStack 再弹出。均摊 O(1) 的 dequeue 是本题的考点，也是"一个数据结构由两个更简单结构组合而成"的设计题原型。

这两题完成后，说明你已经掌握"栈作为配对/倒序工具"的两种基本用法，可以进入下一节的进阶题单。

7. 推荐练习题（Recommended practice questions）与技巧归类

原文档推荐了九道进阶题。按解题技巧归类后更容易制定练习顺序：

（1）数据结构互模拟（设计题）

• Implement Stack using Queues（用队列实现栈）：与第 6 节的必练题互为镜像。push 时把新元素依次搬运到队尾以保证其位于队头，push 为 O(n)、pop 为 O(1)；也可反向权衡，面试时主动讨论两种方案的复杂度取舍。
• Min Stack（最小栈）：在主栈旁维护一个"历史最小值"辅助栈，保证 O(1) 的 getMin。它示范了"辅助栈"技巧：用额外栈与主栈同步压/弹，把原本 O(n) 的操作降为 O(1)。

（2）表达式求值（栈 + 状态机）

• Evaluate Reverse Polish Notation（逆波兰表达式求值）：后缀表达式天然适配栈——操作数入栈、遇运算符弹出两个操作数计算后压回。
• Asteroid Collision（小行星碰撞）：用栈模拟碰撞序列，当前小行星与栈顶反复比较符号与大小，注意"大撞小时当前小行星存活、要继续与新的栈顶比较"这一循环。
• Basic Calculator（基本计算器 I）：数字 + 加减 + 括号，遇到 ( 把当前累积值压栈暂存，遇到 ) 弹出并加回，考察"栈保存嵌套上下文"。
• Basic Calculator II（基本计算器 II）：引入乘除优先级，常见做法是延迟计算：乘除立即与栈顶数字合并，加号则把当前值压栈，末尾一次性求和。

（3）单调栈（Monotonic Stack）——原文档在注释中预留了 "TODO: Monotonic stacks" 的技巧位，而下面三道题正是单调栈的标志性题目，可作为该技巧的练习主线：

• Daily Temperatures（每日温度）：维护一个下标递减栈，新温度若高于栈顶对应温度，则持续弹出并写入"几天后更暖"的答案。每个下标至多入栈、出栈各一次，总体 O(n)。
• Trapping Rain Water（接雨水）：从两端向中间压栈，遇到比栈顶高的柱子时弹出并累加 min(height[i], height[curr]) - height[top] 的积水宽度；也可改用"左/右最大值单调递增"的等价视角。
• Largest Rectangle in Histogram（柱状图中最大矩形）：维护高度递增栈，遇到更矮的柱子时弹出并计算以弹出高度为高的最大矩形右边界。这是单调栈中综合难度最高的一道，建议在完成前两题后挑战。

单调栈的统一心智模型：栈中保存"尚待确定右边界"的元素，新元素到来时批量结算所有被它打破单调性的栈顶元素，因此每个元素只进出栈各一次，总复杂度 O(n)——这一性质也解释了为什么它们能出现在 O(n) 级别的题解中。

8. 学习资源与课程

原文档给出的学习资源：

• 阅读：basecs 的 "Stacks and Overflows"（一篇讲解栈思想与栈溢出的入门文章）；
• 视频：University of California San Diego 的 "Stacks" 课程录像（数据结构课程的栈一章）。

仓库 AlgorithmCourses.md 在每篇算法速查表末尾统一推荐的课程包括：

1. AlgoMonster：宣称由 Google 工程师打造、采用数据驱动方式讲解高频题型的算法课程，一次性付费、非订阅制；
2. Design Gurus《Grokking the Coding Interview》：从"题目模式"（question pattern）视角组织练习，提供 Java、Python、C++、JavaScript 多语言练习与分步可视化；
3. Udemy《Master the Coding Interview: Data Structures + Algorithms》：约 19 小时内容的综合性面试课程，演示语言为 JavaScript，除算法外还覆盖简历、非技术面与谈薪。

9. 与仓库其他专题的衔接

栈在仓库的算法速查表体系中属于 study-cheatsheet.md 所列 19 个专题之一，优先级标记为 Mid（与 Hash Table、Recursion、Linked List 同级）。从速查表的统一结构看（可参考模板 template.md），每个专题都遵循"概述 → 学习资源 → 各语言 API → 复杂度表 → 面试注意点 → Corner cases → 必练题 → 推荐题"的骨架，本篇的栈专题与之完全对应。

两条值得记住的交叉线：

• 栈与队列互为镜像：queue.md 的推荐题中恰好包含 "Implement Queue using Stacks"，而本文必练题中也有 "Implement Stack using Queues"——把两篇速查表合起来练，可以完整覆盖"用 A 模拟 B"这一类设计题；
• 栈是 DFS 的基础设施：仓库 graph.md 所属的图专题、tree.md 所属的树专题中，迭代式遍历都依赖本文第 4 节的显式栈写法，tree_traversal.py 提供了可直接对照的参考实现。

小结

• 栈是 LIFO 抽象数据类型，push/pop/peek/isEmpty 均为 O(1)，Search 为 O(n)；
• C++/Java 有标准库栈类，Python/JavaScript 用 list/Array 的尾部操作模拟即可，且不存在队列那种头部操作 O(n) 的陷阱；
• 写题前后固定检查空栈、单元素、双元素三种边界；
• 练习路径：Valid Parentheses、Implement Queue using Stacks（必练）→ Min Stack、表达式求值系列 → Daily Temperatures、Trapping Rain Water、Largest Rectangle in Histogram（单调栈主线）；
• 面试中能同时给出递归 DFS 与显式栈 DFS 两种写法，是栈这一数据结构的最佳能力证明。