从算法到人工智能 · 第 2 课：数组、链表、栈、队列——数据的四种"住法"
上一课我们搞明白了一件事：算法快不快，看复杂度。同样是找最大数，O(n) 的做法一眨眼，O(n²) 的做法要跑半天。
但这里藏着一个我们上节课没细说的问题——数据本身是怎么存的？
想象你要在一本字典里查一个字。字典有两种编法：
- 编法一：所有字按拼音顺序，一页挨一页排好。
- 编法二：字是散的，每个字下面挂张小纸条，写着"下一个字在第几页"。
同样是"查字典"，这两种编法，查起来的速度完全不一样。
数据结构，研究的就是"数据在内存里怎么存、怎么摆"，因为它直接决定了算法能跑多快。
这一课，我们认识四种最基础、也最重要的数据结构：数组、链表、栈、队列。后面所有花哨的数据结构（哈希表、树、图），全是拿它们当积木搭出来的。
一、数组：一排连号的储物柜
数组（array） 是最简单的一种存法：一段连续的内存，从头到尾挨着排，每个位置有个编号（下标）。
就像学校澡堂的一排储物柜，0 号柜、1 号柜、2 号柜……一个挨一个，中间没有空隙。
数组的快与慢
快的地方：按下标直接拿。 只要你知道柜号，一步到位，不管柜子有多少个。
nums = [10, 20, 30, 40, 50]
print(nums[2]) # 30，直接拿 2 号柜，瞬间的事这在复杂度上叫 O(1)——不管你数组里有 10 个还是 1 亿个数，nums[2] 都是"立刻拿到"。
慢的地方：从中间插一个、删一个，要挪一堆。
还是储物柜的比喻：50 个柜子全用满了，现在有个人非得插到 2 号柜的位置。怎么办？只能让 2 号柜往后所有人集体往后挪一个柜子，腾出空位。挪动的代价是 O(n)。
nums = [1, 2, 3, 4, 5]
nums.insert(2, 99) # 插到下标 2 的位置，后面 3、4、5 都得往后挪
print(nums) # [1, 2, 99, 3, 4, 5]记住：数组读快（O(1)），中间插入/删除慢（O(n)）。
二、链表：每人拿张小纸条，指着下一个人
链表（linked list） 是另一种存法：每个数据单独住一个小隔间（叫"结点"），每个结点里除了存数据，还存一张小纸条，写着"下一个结点在哪儿"。
数据是散的、不连续的，靠纸条一根线串起来。所以叫"链"表。
就像寻宝游戏：你站在起点，第一张纸条说"去 3 号点"，到了 3 号点，纸条说"再去 7 号点"……一个个跳下去。
链表的快与慢
快的地方：插入、删除，改改纸条就行。
还是排队：现在要让新同学插到队伍中间。数组那套"后面全挪一遍"不用了——只需要让前面那个人把纸条改成"指向新同学"，新同学再指向原来他后面的那个人。改 2 张纸条，完事，O(1)。
慢的地方：要找第 5 个结点，得从头一张张纸条摸过去。
数组是"直接开 5 号柜"，链表是"从第 1 个开始，1→2→3→4→5，一个个跳"。要找第 n 个，得跳 n 次，O(n)。
Python 里没有内置链表，我们用类手搓一个，感受一下：
class Node:
def __init__(self, value):
self.value = value # 这个结点存的数据
self.next = None # 小纸条：指向下一个结点
# 串一条链表：10 -> 20 -> 30
a = Node(10)
b = Node(20)
c = Node(30)
a.next = b
b.next = c
# 从头走到尾
cur = a
while cur is not None:
print(cur.value, end=" ")
cur = cur.next
# 输出：10 20 30三、数组 vs 链表：一张表看清
| 操作 | 数组 | 链表 |
|---|---|---|
| 按下标读第 i 个 | O(1) 快 | O(n) 慢，得从头跳 |
| 在末尾加一个 | O(1) 快 | O(1) 快 |
| 在中间插/删 | O(n) 慢，要挪一堆 | O(1) 快，改纸条 |
| 内存占用 | 连续一大块 | 每个结点多一张纸条（指针） |
记一条实用口诀：
经常"按下标读"，用数组；经常"中间插删"，用链表。
现实中 Python 的 list 底层就是"数组"，所以 nums[1000] 快、nums.insert(0, x) 慢。这也是为什么很多人说"别在列表中间频繁插删"。
四、栈：一条道走到黑，后进先出
栈（stack） 是个有规矩的容器：只能从一头进出，先进去的最后出来（LIFO，Last In First Out）。
就像一摞盘子：你只能从顶上放、从顶上拿。最先放进去的盘子，被压在最底下，最后才能拿出来。
实际场景
- 撤回（Ctrl+Z）：你每做一步，就压一个"上一步"进栈；按撤回，就从栈顶弹出最近一步。所以撤回是一步步往回退的。
- 函数调用：程序调函数 A，A 又调 B，B 又调 C。C 跑完回到 B，B 跑完回到 A。这"回去"的顺序，就是栈。
Python 里怎么用栈
Python 没有单独的"栈"类型，但 list 天生就能当栈用，记住两个操作：
stack = [] # 空栈
stack.append(1) # push：压入
stack.append(2)
stack.append(3)
print(stack) # [1, 2, 3]
top = stack.pop() # pop：弹出栈顶（最后压入的）
print(top) # 3
print(stack) # [1, 2]append 是"压入"，pop() 是"弹出栈顶"，正好一进一出，栈就是"后进先出"的列表。
五、队列：排队买奶茶，先进先出
队列（queue） 是另一种规矩：一头进、另一头出，先进去的先出来（FIFO，First In First Out）。
就像排队买奶茶：先来的人先买到、先离开。新来的人只能排在队尾，不能插队。
实际场景
- 打印任务：谁先提交打印，谁的文档先打出来。
- 消息队列：服务器收到的一堆请求，按先后顺序处理。
- 叫号系统：银行、医院取号，号小的先办。
Python 里怎么用队列
用 collections 里的 deque（读作 deck，双端队列），专为"从两头高效进出"设计：
from collections import deque
q = deque() # 空队列
q.append(1) # 入队：排到队尾
q.append(2)
q.append(3)
print(list(q)) # [1, 2, 3]
first = q.popleft() # 出队：从队头拿（先进先出）
print(first) # 1
print(list(q)) # [2, 3]一句话区分栈和队列：
- 栈 = 从同一头进出 → 后进先出（像摞盘子）
- 队列 = 一头进一头出 → 先进先出（像排队）
六、单调栈与单调队列：把没用的先踢掉
前面讲的栈、队列是"容器"，这一节讲两个用它们解题的高级技巧——单调栈、单调队列。名字听着唬人，核心就一句话：
维护一堆"暂时还没轮到"的数据，让它始终保持有序；新来的先把没用的踢掉，剩下的自然就是答案。
单调栈：栈里永远有序
单调栈，就是在普通栈上加一条规矩：栈里的元素始终保持递增或递减。每次压入新元素前，先"踢掉"栈顶那些会破坏单调性的元素。
经典场景——「下一个更大元素」：给你一排数，问每个数右边第一个比它大的数是谁。笨办法是每个数都往后扫一遍（O(n²)）；单调栈能做到 O(n)：
def next_greater(nums):
res = [-1] * len(nums)
stack = [] # 存下标，栈内对应的值单调递减
for i, v in enumerate(nums):
# 新来的 v 比栈顶大，说明栈顶"终于等到了"它的下一个更大
while stack and nums[stack[-1]] < v:
res[stack.pop()] = v
stack.append(i)
return res
print(next_greater([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]为什么快？ 每个元素最多进栈一次、出栈一次，所以整体 O(n)。
单调队列：队头永远是当前最值
单调队列，是在队列基础上维护"队头永远是当前窗口的最大/最小值"。经典场景——滑动窗口最大值：一个固定宽度的窗口从左滑到右，每滑一步问窗口里最大的是谁。
from collections import deque
def max_sliding_window(nums, k):
q = deque() # 存下标，队头对应窗口最大值
res = []
for i, v in enumerate(nums):
# 队尾比 v 小的都出队（它们再也没机会当最大值了）
while q and nums[q[-1]] < v:
q.pop()
q.append(i)
# 队头已经滑出窗口了，丢掉
if q[0] <= i - k:
q.popleft()
# 窗口凑满 k 个才开始记录
if i >= k - 1:
res.append(nums[q[0]])
return res
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]记忆口诀：单调栈管"下一个更大/更小"，单调队列管"滑动窗口最值"。两者的共同点是——把没用的先踢掉，剩下的自然有序。
七、动手时间 🎯
实验 1：感受数组"中间插入"的代价
造一个 10 万个数的列表，然后分别在末尾和开头各插入 10 万次，计时对比：
import time
n = 100000
# 末尾追加（快，O(1) 摊还）
nums = []
start = time.time()
for i in range(n):
nums.append(i)
print("末尾追加耗时:", round(time.time() - start, 3), "秒")
# 开头插入（慢，O(n)，每次后面全要挪）
nums = []
start = time.time()
for i in range(n):
nums.insert(0, i)
print("开头插入耗时:", round(time.time() - start, 3), "秒")你大概率会看到：开头插入比末尾追加慢几百上千倍。 这就是数组"中间写慢"的铁证。
实验 2：用栈检查括号是否配对
经典面试题：给一串括号 ((())) 判断配不配对。思路——遇到左括号压栈，遇到右括号弹栈，最后栈空就配对：
def is_valid(s):
stack = []
for ch in s:
if ch == "(":
stack.append(ch)
elif ch == ")":
if not stack: # 栈空，说明右括号多了
return False
stack.pop()
return len(stack) == 0 # 最后栈空，说明正好配对
print(is_valid("((()))")) # True
print(is_valid("(()")) # False
print(is_valid(")(")) # False实验 3：用队列模拟"叫号"
from collections import deque
q = deque()
for name in ["张三", "李四", "王五"]:
q.append(name)
print(f"{name} 取号排队")
while q:
done = q.popleft()
print(f"叫号 -> {done}")实验 4（挑战）：手搓链表反转
把一条链表 10 -> 20 -> 30 反转成 30 -> 20 -> 10。思路：遍历时把每张小纸条的指向反过来：
class Node:
def __init__(self, value):
self.value = value
self.next = None
a, b, c = Node(10), Node(20), Node(30)
a.next = b; b.next = c
def reverse(head):
prev = None
cur = head
while cur:
nxt = cur.next # 先记住下一个，别弄丢
cur.next = prev # 纸条反过来，指向前面
prev = cur
cur = nxt
return prev
new_head = reverse(a)
cur = new_head
while cur:
print(cur.value, end=" ")
cur = cur.next
# 输出：30 20 10八、小结
- 数据结构 = 数据在内存里怎么存，它决定了算法能跑多快。
- 数组读快中间写慢，链表中间写快读慢——经常按下标读用数组，经常中间插删用链表。
- 栈是"后进先出"，队列是"先进先出"——栈像摞盘子（一头进出），队列像排队（一头进一头出）。
- 单调栈/单调队列是"把没用的先踢掉"——单调栈管"下一个更大/更小"，单调队列管"滑动窗口最值"，都能把 O(n²) 压到 O(n)。
先别急着往后看，把这四个实验敲熟，四种数据结构的"手感"就长在你脑子里了。