一句话总结
栈（LIFO，后进先出）和队列（FIFO，先进先出）是最基础的两个线性结构。它们本身简单，但衍生出两个高频考点：用栈/队列互相实现，以及单调栈——通过在入栈时弹出破坏单调性的元素，把"找左边/右边第一个更大或更小的元素"从 O(n²) 降到 O(n)。
🥞
栈 Stack
后进先出。适合"最近的匹配"：括号、表达式、撤销操作、DFS。
🚶
队列 Queue
先进先出。适合"按顺序处理"：BFS、消息队列、滑动窗口最大值。
📶
单调栈
栈内元素保持递增/递减，O(n) 找"下一个更大元素"。
📉
单调队列
双端队列维护窗口最值，O(n) 求滑动窗口最大/最小值。
一、栈与队列的互相实现
1.1 用两个栈实现队列（LeetCode 232）
class MyQueue:
def __init__(self):
self.in_s, self.out_s = [], []
def push(self, x):
self.in_s.append(x) # 入队：直接压 in
def _transfer(self):
if not self.out_s: # out 空了才倒腾（关键！）
while self.in_s:
self.out_s.append(self.in_s.pop())
def pop(self):
self._transfer()
return self.out_s.pop()
def peek(self):
self._transfer()
return self.out_s[-1]
def empty(self):
return not self.in_s and not self.out_s
1.2 用两个队列实现栈（LeetCode 225）
思路：入栈时压入 q1；出栈时把 q1 中除最后一个元素外的全部搬到 q2，剩下的那个就是"栈顶"，弹出后再交换 q1/q2。这样每次 pop 是 O(n)，push 是 O(1)。
（另一种更简洁的做法：用一个队列，push 后把前面所有元素依次重新入队，让新元素排到队首。）
（另一种更简洁的做法：用一个队列，push 后把前面所有元素依次重新入队，让新元素排到队首。）
二、栈的经典应用
2.1 括号匹配（LeetCode 20）
def isValid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([' + '{':
stack.append(ch) # 左括号入栈
else: # 右括号：必须匹配栈顶
if not stack or stack.pop() != pairs[ch]:
return False
return not stack # 栈必须为空（不能有多余左括号）
2.2 其他高频栈题目
| 题目 | 栈里存什么 | 什么时候弹出 |
|---|---|---|
| 20 有效的括号 | 左括号 | 遇到匹配的右括号 |
| 155 最小栈 | 值 + 当前最小值（辅助栈） | pop 时同步弹辅助栈 |
| 150 逆波兰表达式 | 操作数 | 遇到运算符弹两个算一个再压回 |
| 739 每日温度 | 下标（单调栈） | 遇到更高温度时 |
| 84 柱状图最大矩形 | 高度下标（单调递增栈） | 遇到更矮柱子时结算 |
| 394 字符串解码 | 重复次数 + 之前的字符串 | 遇到右括号 ] |
| 71 简化路径 | 路径片段 | 遇到 ".." 时弹出 |
三、单调栈：O(n) 找"下一个更大元素"
3.1 核心思想
朴素做法对每个元素向右扫描找第一个更大的，是 O(n²)。单调栈的做法是：维护一个栈，栈内元素保持单调（递增或递减）。遍历数组时，如果当前元素破坏了单调性，就不断弹出栈顶——被弹出的那些元素，它们的"答案"恰好就是当前这个元素。
3.2 单调栈模板
def dailyTemperatures(temperatures):
n = len(temperatures)
ans = [0] * n
stack = [] # 存下标，对应温度保持单调递减
for i, t in enumerate(temperatures):
while stack and t > temperatures[stack[-1]]:
j = stack.pop() # 当前元素就是 j 的"下一个更大"
ans[j] = i - j
stack.append(i) # 当前下标入栈，等待未来被更大的元素结算
return ans # 留在栈里的说明右边没有更大的，保持 0
# 变体速记：
# 找"下一个更大元素" → 栈底到栈顶单调递减，遇大则弹
# 找"下一个更小元素" → 栈底到栈顶单调递增，遇小则弹
# 求"上一个更大" → 从左往右扫，弹出前记录栈顶即为答案
# 存下标而非存值 → 才能计算距离（如天数差、宽度）
3.3 单调栈经典题目
| 题目 | 栈的单调性 | 弹出时机与结算 |
|---|---|---|
| 739 每日温度 | 递减 | 遇更大 → 结算天数差 |
| 496 下一个更大元素 I | 递减 | 遇更大 → 记录映射 |
| 503 下一个更大元素 II（环形） | 递减 | 遍历两遍数组（i % n） |
| 84 柱状图最大矩形 | 递增 | 遇更矮 → 以弹出柱子为高结算面积 |
| 42 接雨水 | 递减 | 遇更高 → 按层结算积水 |
| 316 去除重复字母 | 递增 + 计数 | 保证字典序最小 |
四、单调队列：滑动窗口最值
4.1 为什么需要它？
求"每个长度为 k 的窗口里的最大值"，暴力是 O(n×k)。用堆是 O(n log k)。而单调队列能做到 O(n)：维护一个双端队列，队首始终是当前窗口的最大值下标，队内元素值单调递减。
from collections import deque
def maxSlidingWindow(nums, k):
q = deque() # 存下标，对应值单调递减
res = []
for i, x in enumerate(nums):
while q and nums[q[-1]] <= x: # ① 维护单调性：小的全弹走
q.pop()
q.append(i)
if q[0] <= i - k: # ② 队首已滑出窗口 → 移除
q.popleft()
if i >= k - 1: # ③ 窗口已成形 → 记录队首
res.append(nums[q[0]])
return res
对比记忆：
单调栈：在一端进出，解决"某个元素左/右边第一个更大/更小"的问题。
单调队列：两端都能进出，解决"滑动窗口中的最大/最小值"问题。
两者共同点：每个元素最多进出一次 → 均摊 O(n)。
单调栈：在一端进出，解决"某个元素左/右边第一个更大/更小"的问题。
单调队列：两端都能进出，解决"滑动窗口中的最大/最小值"问题。
两者共同点：每个元素最多进出一次 → 均摊 O(n)。
⚠️ 实现细节：
① 单调栈 / 队列里存下标而不是存值，才能算距离或判断元素是否已滑出窗口；
② 判空顺序：先 while 维护单调性，再入队，再检查队首是否过期，最后才记录答案；
③ 相等元素是否弹出要看题意（求最大值通常
① 单调栈 / 队列里存下标而不是存值，才能算距离或判断元素是否已滑出窗口；
② 判空顺序：先 while 维护单调性，再入队，再检查队首是否过期，最后才记录答案；
③ 相等元素是否弹出要看题意（求最大值通常
<= 全弹；去重类题目可能保留）。