第三章：栈与队列

本章目标

本章学习栈、队列和单调栈。它们都限制元素进出的方向，用简单规则换来清晰的状态管理。

你会用栈处理括号匹配，用队列维护先进先出流程，用单调栈寻找下一个更大元素。

核心概念

栈是后进先出，适合处理最近打开、最近未完成的问题。括号匹配、函数调用、撤销操作都能用栈建模。

队列是先进先出，适合按到达顺序处理任务。Python 推荐用 collections.deque 做两端 O(1) 的追加和弹出。

Python 示例

deque 可以高效实现队列操作，避免 list.pop(0) 的 O(n) 移动。

from collections import deque

queue = deque(["a", "b"])
queue.append("c")
first = queue.popleft()  # O(1)

括号匹配使用栈保存等待闭合的左括号；单调栈可以求每个元素右侧第一个更大值。

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans

复杂度与常见误区

栈和队列的单次入队、出队通常是 O(1)。单调栈里每个元素最多入栈一次、出栈一次，所以总时间是 O(n)。

常见误区是看到 while 就认为是 O(n^2)。单调栈的 while 弹出的是未来不会再出现的元素，总次数可摊还分析。

本章要点

栈解决最近依赖，队列解决顺序处理，deque 是 Python 中实现两者的常用工具。

单调结构的核心是维护一个对答案有用的候选集合，把无用候选及时删除。