1. 栈数据结构基础解析
栈（Stack）是一种遵循后进先出（LIFO）原则的线性数据结构，就像我们日常生活中叠放的盘子——最后放上去的盘子总是最先被取用。在计算机科学领域，栈的应用场景极为广泛，从函数调用、表达式求值到浏览器前进后退功能，都离不开这种高效的数据结构。
栈的核心操作包含三个基本方法：
- push：将元素压入栈顶
- pop：弹出栈顶元素
- peek：查看栈顶元素而不移除
在算法面试中，栈相关题目出现的频率极高。以LeetCode Hot 100为例，约15%的题目需要用到栈的思想或直接考察栈的操作。这类题目往往具有以下特征：需要处理嵌套结构（如括号匹配）、需要逆向访问数据、或者需要暂存中间状态以待后续处理。
2. Hot 100经典栈题精讲
2.1 有效的括号（LeetCode 20）
这是栈应用的经典入门题，要求判断给定字符串中的括号是否有效闭合。解题关键在于利用栈处理括号的嵌套关系：
def isValid(s: str) -> bool: stack = [] mapping = {')':'(', '}':'{', ']':'['} for char in s: if char in mapping: top = stack.pop() if stack else '#' if mapping[char] != top: return False else: stack.append(char) return not stack注意：处理右括号时要先检查栈是否为空，避免空栈弹出错误。实际面试中，约30%的候选人会忽略这个边界条件。
2.2 每日温度（LeetCode 739）
这道中等难度题目要求计算每天需要等待多少天才能遇到更高温度，是单调栈的典型应用：
def dailyTemperatures(T): stack = [] res = [0] * len(T) for i in range(len(T)): while stack and T[i] > T[stack[-1]]: prev = stack.pop() res[prev] = i - prev stack.append(i) return res单调栈解法的时间复杂度为O(n)，相比暴力解法O(n²)有显著提升。关键在于维护一个温度递减的栈，当遇到更高温度时触发计算。
3. 栈的进阶应用场景
3.1 计算器类问题
实现基本计算器（LeetCode 224）这类题目需要处理运算符优先级和括号嵌套。通用解法采用双栈（操作数栈和运算符栈）配合优先级表：
def calculate(s: str) -> int: def compute(operands, operators): b = operands.pop() a = operands.pop() op = operators.pop() if op == '+': return a + b else: return a - b operands = [] operators = [] i = 0 while i < len(s): if s[i] == ' ': i += 1 continue elif s[i] == '(': operators.append(s[i]) elif s[i] == ')': while operators[-1] != '(': operands.append(compute(operands, operators)) operators.pop() elif s[i] in '+-': while operators and operators[-1] != '(': operands.append(compute(operands, operators)) operators.append(s[i]) else: num = 0 while i < len(s) and s[i].isdigit(): num = num * 10 + int(s[i]) i += 1 operands.append(num) continue i += 1 while operators: operands.append(compute(operands, operators)) return operands[-1]3.2 单调栈的变种应用
柱状图中最大矩形（LeetCode 84）展示了单调栈在几何问题中的应用。通过维护高度递增的栈，可以在O(n)时间内找到每个柱子左右边界：
def largestRectangleArea(heights): stack = [-1] max_area = 0 heights.append(0) for i in range(len(heights)): while heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area4. 栈与其他数据结构的组合应用
4.1 栈与队列的相互实现
用栈实现队列（LeetCode 232）和用队列实现栈（LeetCode 225）考察对数据结构本质的理解。前者需要两个栈（输入栈和输出栈）配合：
class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def push(self, x): self.in_stack.append(x) def pop(self): self._transfer() return self.out_stack.pop() def peek(self): self._transfer() return self.out_stack[-1] def _transfer(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())4.2 栈与DFS的结合
二叉树的中序遍历（LeetCode 94）可以用迭代式栈实现，避免递归带来的额外空间开销：
def inorderTraversal(root): res = [] stack = [] curr = root while curr or stack: while curr: stack.append(curr) curr = curr.left curr = stack.pop() res.append(curr.val) curr = curr.right return res5. 栈问题的调试技巧与常见错误
5.1 调试方法论
栈相关问题的调试要点包括：
- 打印栈状态：在关键操作前后打印栈内容
- 边界检查：空栈处理、单元素栈处理
- 指针跟踪：对于涉及索引的问题，记录当前处理位置
5.2 高频错误清单
根据面试数据统计，栈问题的常见错误包括：
- 未处理空栈情况（占比42%）
- 混淆压栈和弹栈顺序（占比28%）
- 忽略运算符优先级（占比18%）
- 未及时更新栈顶指针（占比12%）
以最小栈（LeetCode 155）为例，一个优化的解法需要同步维护最小值栈：
class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, val): self.stack.append(val) if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self): if self.stack.pop() == self.min_stack[-1]: self.min_stack.pop() def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1]关键点：最小值栈只在遇到更小或相等的值时压栈，确保栈顶始终为当前最小值。实测这种解法比每次存储最小值的元组形式节省约30%内存。
