栈、队列与双端队列

栈（Stack）

后进先出。数组 + top 或链表实现均可，操作均摊 O(1)。

有效括号：

def is_valid(s):
    stack = []
    pair = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in pair:
            if not stack or stack[-1] != pair[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

单调栈：求每个元素左右第一个更大/更小。维护递减栈，遍历 nums[i] 时弹出 < nums[i] 的下标，弹出者以 i 为右边界答案。

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

队列（Queue）

先进先出。BFS、滑动窗口、任务调度。循环数组实现可避免假溢出：front/rear 取模。

from collections import deque
def bfs_level(root):
    if not root:
        return []
    q = deque([root])
    res = []
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

双端队列（Deque）

两端 O(1) 入队出队。用于滑动窗口最值（维护单调递减下标队列）、0-1 BFS、Dijkstra 小优化。

互实现（面试小题）

| 结构 | 实现思路 | |---|---| | 栈 → 队列 | 两个栈 in/out | | 队列 → 栈 | 两个队列，或用一个队列轮转 | | 最小栈 | 辅助栈同步最小值 |

练习：20、155、232、239、84（柱状图最大矩形 + 单调栈）。说清楚「栈里存什么」（值还是下标）是拿分关键。