📚 栈 — 后进先出的智慧

📖 栈的核心概念

栈（Stack）是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除。栈的操作极为简单——push（入栈）和 pop（出栈），但这简单的规则却能解决括号匹配、表达式求值、深度优先搜索等众多问题。面试中，栈的进阶应用——单调栈，是高频考点。

1. 栈的三大应用场景

2. Python 栈操作速查

# 用 list 模拟栈（推荐）
stack = []
stack.append(1)    # push
stack.pop()        # pop (末尾)
stack[-1]          # peek
len(stack) == 0    # empty

# collections.deque（线程安全，两端O(1)）
from collections import deque
stack = deque()
stack.append(1)
stack.pop()

🎯 题目一：有效的括号 (LC 20)

题目描述：给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串 s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。

思路分析

代码实现

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {')': '(', '}': '{', ']': '['}
        stack = []
        for ch in s:
            if ch in mapping:  # 右括号
                top = stack.pop() if stack else '#'
                if top != mapping[ch]:
                    return False
            else:  # 左括号
                stack.append(ch)
        return not stack

复杂度分析

时间复杂度：O(n) — 一次遍历

空间复杂度：O(n) — 最坏全部入栈

变体练习

• LC 32 最长有效括号（Hard，栈+动态规划）
• LC 22 括号生成（回溯法生成合法括号）

🎯 题目二：最小栈 (LC 155)

题目描述：设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

思路分析

代码实现

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if self.min_stack:
            self.min_stack.append(min(val, self.min_stack[-1]))
        else:
            self.min_stack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

复杂度分析

时间复杂度：所有操作 O(1)

空间复杂度：O(n) — 辅助栈

变体练习

• LC 716 最大栈（与最小栈对称，但 popMax 需要 O(n)）
• LC 844 比较含退格的字符串（栈模拟退格）

🎯 题目三：用栈实现队列 (LC 232)

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

思路分析

代码实现

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def _transfer(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

复杂度分析

push：O(1) | pop/peek：均摊 O(1)

空间复杂度：O(n)

变体练习

• LC 225 用队列实现栈（对称问题）
• LC 150 逆波兰表达式求值（栈计算后缀表达式）

📝 课后练习

1. LC 496 下一个更大元素 I（单调栈入门）
2. LC 739 每日温度（单调栈经典）
3. LC 150 逆波兰表达式求值
4. LC 71 简化路径（栈处理路径）
5. LC 225 用队列实现栈

🔑 本课要点回顾

• 栈 = LIFO，天然适合"最近匹配"问题
• 括号匹配：左括号入栈，右括号匹配栈顶
• 最小栈：辅助栈同步记录每时刻最小值，O(1) 查询
• 双栈实现队列：输入栈+输出栈，倒入实现 FIFO
• 均摊分析：每个元素最多 4 次栈操作，均摊 O(1)
• 单调栈是下一个重点，将在后续课程深入

📚 扩展阅读

• 《算法导论》第10章 栈和队列
• 栈专题：LeetCode 栈标签
• 单调栈详解：labuladong 单调栈模板

🔬 单调栈初探

单调栈是栈最重要的进阶应用，虽然完整讲解在后续课程，但这里先介绍其核心思想，为深入学习打下基础。

单调栈的核心：在弹出时处理答案。被弹出的元素找到了"右边第一个比它大的元素"，就是当前遍历到的元素。这种"延迟处理"的思想非常优雅。