Ch14 §02 链表、栈、队列 · 讲解稿¶

章节定位: 链式结构 + 线性容器。教"插入 \(O(1)\)"与"顺序访问": 单链表 / 双链表 / 循环链表 / 栈 / 队列 / 单调栈 / LRU。承接: §01 数组 → §02 链式结构走向: §03 树 / §04 图 / §05 排序篇幅: ~3700 字 / 阅读 11 分钟 / 讲解 22-25 分钟

一 · 一句话总览¶

链表 / 栈 / 队列 = 链式结构 (插入 \(O(1)\), 访问 \(O(n)\)) + LIFO/FIFO 容器。LRU Cache 是链表 + 哈希的经典组合, 是 AI 系统设计必学。

二 · 章节主线 (5 段)¶

第 1 段 · 链表基础 (8 分钟)¶

3.1.1 节点定义¶

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

3.1.2 单链表¶

# 头插
def prepend(head, val):
    return ListNode(val, head)

# 尾插
def append(head, val):
    if not head: return ListNode(val)
    cur = head
    while cur.next: cur = cur.next
    cur.next = ListNode(val)
    return head

# 反转
def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

3.1.3 双向链表¶

每个节点两个指针: prev + next。删除已知节点 \(O(1)\), 用于 LRU。

class DListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

3.1.4 循环链表¶

尾节点的 next 指向头。约瑟夫问题。

第 2 段 · 快慢指针 (8 分钟)¶

3.2.1 链表中点¶

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

3.2.2 环检测 (Floyd)¶

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

3.2.3 找倒数第 k¶

def kth_from_end(head, k):
    fast = slow = head
    for _ in range(k):
        if not fast: return None
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    return slow

第 3 段 · 栈与队列 (8 分钟)¶

3.3.1 栈 (LIFO)¶

class Stack:
    def __init__(self):
        self.data = []
    def push(self, x): self.data.append(x)
    def pop(self): return self.data.pop()
    def top(self): return self.data[-1]
    def empty(self): return len(self.data) == 0

3.3.2 单调栈¶

栈内元素单调 (递增 / 递减), 用于"下一个更大元素"。

def next_greater(nums):
    n = len(nums)
    res = [-1] * n
    stack = []  # 存下标
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

\(O(n)\) 时间, 经典应用: 接雨水, 柱状图最大矩形。

3.3.3 队列 (FIFO)¶

from collections import deque

class Queue:
    def __init__(self):
        self.data = deque()
    def enqueue(self, x): self.data.append(x)
    def dequeue(self): return self.data.popleft()
    def empty(self): return len(self.data) == 0

3.3.4 双端队列¶

两端都可插入删除。Python collections.deque。

3.3.5 优先队列¶

底层是堆 (heap)。Python heapq 是最小堆。

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappop(heap)  # 1 (最小)

第 4 段 · LRU Cache (10 分钟)¶

LRU (Least Recently Used) 是经典案例, 链表 + 哈希。

3.4.1 思路¶

哈希表: key → 双向链表节点 (O(1) 查找)
双向链表: 维护访问顺序, 头新尾旧
get: 找到节点, 移到头
put: 已存在则更新移到头; 否则插入头, 超容删尾

3.4.2 实现¶

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key -> node
        # 双向链表 (用 dict 模拟)
        self.head = {}
        self.tail = {}
        self.head['next'] = self.tail
        self.tail['prev'] = self.head

    def _remove(self, node):
        p, n = node['prev'], node['next']
        p['next'] = n
        n['prev'] = p

    def _add_to_front(self, node):
        node['next'] = self.head['next']
        node['prev'] = self.head
        self.head['next']['prev'] = node
        self.head['next'] = node

    def get(self, key):
        if key not in self.cache: return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node['val']

    def put(self, key, val):
        if key in self.cache:
            node = self.cache[key]
            node['val'] = val
            self._remove(node)
            self._add_to_front(node)
        else:
            if len(self.cache) >= self.cap:
                # 删尾
                lru = self.tail['prev']
                self._remove(lru)
                del self.cache[lru['key']]
            new_node = {'key': key, 'val': val}
            self.cache[key] = new_node
            self._add_to_front(new_node)

\(O(1)\) 全部操作。

3.4.3 Python `OrderedDict` 简化版¶

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, val):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = val
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

3.4.4 LRU 应用¶

OS 页置换 (Ch13 §03)
数据库缓冲池
Web 缓存 (Redis)
LLM KV cache (LRU 淘汰)

第 5 段 · 应用与陷阱 (5 分钟)¶

3.5.1 表达式求值¶

中缀 → 后缀 (Shunting Yard) → 后缀求值 (栈)。

3.5.2 BFS 用队列¶

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)

3.5.3 陷阱¶

空指针: head is None 必须先检查。
循环引用: 双链表手动管理内存易漏。
Python list 头插: \(O(n)\), 用 deque。
栈溢出: 递归深用显式栈。
LRU 容量: 0 会出错。

三 · 易错点 (5 条)¶

链表 vs 数组: 链表插入快但访问慢。
快慢指针: 一个先走 k 步, 一起走到底。
单调栈: 入栈前清栈, 维护单调性。
LRU: 哈希 + 双链, 不是单链。
deque: 两端 \(O(1)\), 中间仍是 \(O(n)\)。

四 · 跨章连接¶

章节	关联
Ch13 §03 OS	LRU 页置换
Ch13 §04 MapReduce	shuffle 用队列
Ch12 §03 GNN	邻接表是链表
Ch07 §04 Transformer	推理缓存

五 · 自测 5 题¶

单链表反转核心代码?
Floyd 环检测原理?
单调栈应用?
LRU Cache 数据结构?
双端队列 vs list?

六 · 一句话总结¶

链表 / 栈 / 队列 = 链式 + LIFO/FIFO。LRU 是经典组合 (哈希 + 双链), 用于 OS 页置换 / 数据库缓冲 / LLM KV cache。Ch14 §03 进入树。

七 · 板书建议¶

[板书 1: 链表]
   单链 / 双链 / 循环
   反转 + 快慢指针

[板书 2: 栈/队列]
   LIFO / FIFO
   单调栈 / 优先队列

[板书 3: LRU]
   哈希 + 双链
   头新尾旧

八 · 参考资料¶

Cormen et al., CLRS Ch 10 (链表)
LeetCode 146 (LRU Cache)
Ch13 §03 操作系统 (本套书)
Python collections 文档