03　什么是数据结构？

数据结构不是一个容器名称的清单。它描述数据如何表示、如何连接，以及操作如何保持这些关系。本章把原书的抽象数据类型、枚举、数组、记录与指针概念换成 Python 中的接口、对象和引用。

1. 抽象数据类型先描述行为

栈允许压入、取出顶部和检查是否为空，并遵循后进先出。这里没有要求用数组还是链表。操作及其行为约定构成抽象数据类型（ADT）；具体列表、节点与实现方法属于实现。

字典 ADT 提供按键插入、搜索、删除等操作。Python 的 dict 是一种具体的字典实现，不能把抽象字典与哈希实现完全等同。

2. 从伪代码逐步细化

先写“记录新任务”“取最后一个任务”，再选列表实现栈，最后把“压入”细化为 append。如果后续改成链表，实现需要变化，调用方的 push/pop 约定可以保留。

接口相同不代表性能相同，也不代表允许的异常处理可以随意改变。

3. 用类封装一个栈

class ListStack:
    def __init__(self):
        self._items = []

    def push(self, value):
        self._items.append(value)

    def pop(self):
        if not self._items:
            raise IndexError("栈为空")
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):
        return len(self._items)

s = ListStack()
s.push(10)
s.push(20)
print(s.pop())  # 20

下划线表示实现细节的约定，不是强制的访问保护。可靠的封装还需要调用者遵守接口、实现者维护不变式。

4. 基础值、容器与对象

Python 提供整数、浮点数、布尔值、字符串以及 list、tuple、dict、set 等。选择它们要考虑逻辑需求：是否有顺序、是否允许重复、能否按键定位、是否需要修改。

Python 整数可以任意精度增长；严格分析大整数运算时，不能把每次加法都无条件看作与位数无关的 O(1)。本套大多数示例采用固定成本的键与基本运算模型。

5. 枚举比魔法数字更清楚

from enum import Enum

class Signal(Enum):
    RED = "红"
    YELLOW = "黄"
    GREEN = "绿"

def can_go(signal):
    return signal is Signal.GREEN

print(can_go(Signal.GREEN))  # True

枚举让合法状态显式可见。它不会自动实现状态机：红灯如何变绿、故障时如何处理，仍要写成规则。

6. 把关联字段组成记录

from dataclasses import dataclass

@dataclass
class Student:
    name: str
    score: int

student = Student("小林", 90)
print(student.name, student.score)

记录把属于同一对象的字段放在一起，减少多个列表之间错位的风险。类型标注帮助阅读与检查，普通 Python 运行时不会仅凭标注拒绝所有错误类型。

7. 列表与对象引用

student = Student("小林", 90)
a = [student]
b = a.copy()
b[0].score = 95
print(a[0].score)  # 95

浅拷贝创建新的外层列表，却没有复制里面的 Student 对象。a[0] 与 b[0] 指向同一个对象。引用关系是理解链表、树和别名修改的基础。

Python 名称绑定到对象；重新给名称赋值，和修改已有对象的字段，是两件不同的事。

8. “传引用”的准确理解

def change(items):
    items.append(3)  # 修改调用者也能看到的列表
    items = [99]     # 只重新绑定局部名称
    return items

values = [1, 2]
other = change(values)
print(values)  # [1, 2, 3]
print(other)   # [99]

Python 参数传递通常称为共享对象传递。不要把它直接等同于 C 的地址算术或可以改写调用者变量的“引用参数”。

9. 用引用把节点连起来

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

first = Node(10, Node(20))
print(first.next.value)  # 20

None 表示没有下一节点；节点可能在不同位置，逻辑顺序由 next 决定。Python 不提供 C 指针的手动地址运算，但对象引用足以表达链表与树。

10. 数据结构要维护不变式

链表的 next 需要指向下一节点或 None；双向链表的相邻 prev/next 应相互一致；BST 的左右子树满足有序关系；环形队列的 size 不能超过 capacity。

每个公开操作完成后，都应恢复其不变式。修改一个字段看起来简单，也可能影响多个关系。

11. 生命周期与内存管理

Python 使用自动内存管理。del name 删除名称绑定，不意味着所有其他引用也被删除，更不保证对象立刻被销毁。对象仍被节点或容器引用时，它仍然可达。

文件等外部资源推荐使用 with 明确释放。自动内存管理不能替代资源管理，也不能自动修复错误链接。

12. 同一个 ADT，不同实现

比较实现时，要同时看行为兼容、时间、空间与使用场景。本章的栈实现用于接口教学；后续章节会把具体结构展开。