栈与队列

栈（Stack）

栈是后进先出（LIFO，Last In First Out）的线性结构。只能在一端（栈顶）进行插入和删除。

# Python 用 list 实现栈
stack = []
stack.append(1)    # push → [1]
stack.append(2)    # push → [1, 2]
stack.append(3)    # push → [1, 2, 3]
stack.pop()        # pop  → 3，剩余 [1, 2]
stack[-1]          # peek → 2（查看栈顶）

# 从链表实现栈（教学用）
class Stack:
    def __init__(self):
        self._data = []    # 实际用 list 即可

    def push(self, val): self._data.append(val)
    def pop(self):       return self._data.pop()
    def peek(self):      return self._data[-1]
    def is_empty(self):  return len(self._data) == 0
    def size(self):      return len(self._data)

应用：括号匹配

def is_valid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)            # 左括号入栈
        elif not stack or stack[-1] != pairs[ch]:
            return False               # 右括号不匹配
        else:
            stack.pop()                 # 匹配成功，弹出
    return len(stack) == 0            # 栈空说明全部匹配

队列（Queue）

队列是先进先出（FIFO，First In First Out）的线性结构。从队尾入队，从队头出队。

from collections import deque

q = deque()
q.append(1)        # 入队（队尾）
q.append(2)
q.append(3)
q.popleft()        # 出队（队头）→ 1
q[0]               # 查看队头 → 2

# BFS 模板（图/树的层序遍历）
def bfs(start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()
        process(node)
        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

单调栈

单调栈是在普通栈的基础上，维护栈内元素单调递增或递减的性质。每个元素最多入栈出栈一次，总体 O(n)。

核心思路：当新元素入栈时，将所有"比它大（或比它小）"的栈顶元素弹出，同时这些被弹出的元素的"下一个更大/更小元素"就是当前新元素。

下一个更大元素

def next_greater_element(nums: list) -> list:
    n = len(nums)
    result = [-1] * n    # 默认 -1（右侧无更大元素）
    stack = []            # 单调递减栈，存下标

    for i in range(n):
        # 当前元素比栈顶大 → 栈顶找到了"下一个更大元素"
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)

    return result

# 示例：[2, 1, 2, 4, 3]
# 结果：[4, 2, 4, -1, -1]

柱状图中最大的矩形

def largest_rectangle(heights: list) -> int:
    # 单调递增栈：找每根柱左右两侧第一个比它矮的柱
    stack = [-1]   # 哨兵，方便处理边界
    heights = heights + [0]  # 末尾加 0 强制清空栈
    max_area = 0

    for i, h in enumerate(heights):
        while stack[-1] != -1 and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1   # 宽度 = 当前位置 - 左边界 - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area
# 时间 O(n)，每个元素最多入栈出栈一次

优先队列（堆）

优先队列每次出队的是优先级最高的元素（通常是最小值或最大值）。Python 的 heapq 是最小堆。

import heapq

# 最小堆
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappop(heap)   # 返回 1（最小值）

# 最大堆：存负数模拟
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
-heapq.heappop(max_heap)   # 返回 3（最大值）

# Top K 最大元素 — O(n log k)
def top_k_largest(nums: list, k: int) -> list:
    # 维护大小为 k 的最小堆
    # 堆中保存的是 k 个最大值，堆顶是其中最小的
    heap = nums[:k]
    heapq.heapify(heap)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)  # 弹出最小值，加入新元素
    return heap

heappush/popO(log n) heapifyO(n)

双端队列（Deque）

双端队列两端都可以 O(1) 进行入队和出队。可以同时模拟栈和队列。

滑动窗口最大值

from collections import deque

def max_sliding_window(nums: list, k: int) -> list:
    # 单调递减双端队列，存下标
    # 队列头部始终是当前窗口内最大值的下标
    dq = deque()
    result = []

    for i, x in enumerate(nums):
        # 移除窗口外的下标（队头）
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        # 移除所有比当前元素小的下标（队尾），保持单调递减
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        # 窗口形成后开始记录答案
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result
# 时间 O(n)，空间 O(k)

用两个栈实现队列

class MyQueue:
    def __init__(self):
        self.inbox = []    # 入队栈
        self.outbox = []   # 出队栈

    def push(self, val):
        self.inbox.append(val)

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

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

    def _transfer(self):
        # outbox 空时，将 inbox 所有元素倒入 outbox（逆转顺序）
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

# 摊还分析：每个元素最多入栈出栈各 2 次 → 摊还 O(1)