栈与队列

栈与队列是两种受限的线性表：栈后进先出（LIFO），队列先进先出（FIFO）。它们结构简单，却是无数算法的地基——括号匹配、函数调用栈、单调栈、消息队列、BFS 层序遍历都离不开它们。面试题里"用栈模拟队列""滑动窗口最大值"等难题也由此展开。

栈：后进先出

栈只允许在一端（栈顶）压入和弹出，就像一摞盘子：后放上去的先拿走。核心操作 push（入栈）、pop（出栈）、peek（看栈顶），全部 O(1)。

st = []
st.append(1); st.append(2); st.append(3)   # 入栈 push
top = st[-1]                                # peek 看栈顶
print(top, st.pop(), st.pop())              # 出栈 pop，输出：3 3 2

最经典的场景是括号匹配：左括号入栈，遇到右括号时弹出栈顶比对：

def is_balanced(s):
    st, pairs = [], {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            st.append(ch)                  # 左括号入栈
        elif not st or st.pop() != pairs[ch]:
            return False                   # 栈空或类型不匹配
    return not st                          # 栈空才算全部配对

print(is_balanced("([{}])"))   # 输出：True
print(is_balanced("([)]"))     # 输出：False

此外，函数调用的调用栈、浏览器的前进后退（双栈）、表达式求值（中缀转后缀）都用栈。

队列：先进先出

队列只允许队尾入队、队头出队，像排队买票。Python 用 collections.deque，两端操作都是 O(1)：

from collections import deque

q = deque([1, 2, 3])
q.append(4)                # 队尾入队
first = q.popleft()        # 队头出队
print(first)               # 输出：1

自己实现队列时，常用循环数组避免"出队后前面的空间浪费"：下标取模绕圈，队满 = (tail + 1) % cap == head（牺牲一格区分空与满）。

数组实现循环队列 cap=5：
[_, 1, 2, 3, _]  head=1 tail=4
入队 5：tail = (4+1)%5 = 0 → [5, 1, 2, 3, _]  ← 下标绕回开头

队列的另一重要应用是 BFS（广度优先搜索）：逐层弹出节点并入队其邻居，配合"分层记录"即可完成树的层序遍历、无权图最短路。

单调栈：找下一个更大元素

单调栈维护栈内元素单调（如从栈底到栈顶递减），用于 O(n) 求解"每个元素右边第一个比它大的值"：

def next_greater(nums):
    res, st = [-1] * len(nums), []      # st 存下标
    for i, x in enumerate(nums):
        while st and nums[st[-1]] < x:  # 栈顶被 x "干掉"：x 就是它的答案
            res[st.pop()] = x
        st.append(i)
    return res

print(next_greater([2, 1, 4, 3]))   # 输出：[4, 4, -1, -1]

每个元素至多入栈出栈一次，所以整体 O(n)。套路：题中出现"下一个更大/更小元素"，优先想单调栈。

单调队列：滑动窗口最大值

窗口每次右移一格，若用普通队列需 O(k) 找最大值；单调队列（队内单调递减，队头即最大值）让每个元素进出一次，整体 O(n)。实现时队列存下标，出窗时若队头下标过期则弹出。这题也是"栈与队列"的压轴综合题，值得手写一遍。

小结

栈与队列是"规则最简单、用途最广"的结构：栈适合"最近相关"（括号、回退、调用栈），队列适合"顺序处理"（任务调度、BFS）。熟练后再加上单调栈、单调队列两个优化套路，就覆盖了大部分相关面试题。