数据结构导论：从数组到抽象数据类型（ADT）

很多人学完数组、链表、栈、队列，仍有一个挥之不去的困惑：这些"数据结构"到底有没有区别？为什么教科书总说 Stack 是 ADT 而不是数据结构？ 如果你也含糊，这篇就是为你写的——我们不背定义，先把这层窗户纸捅破。

缘起很朴素：数组是最原始、最"诚实"的数据结构，它把 N 个同类型元素连续摆在内存里，你用下标直接取。但它太"裸"了——它既不阻止你越界访问，也不阻止你在第 0 位插一个元素（后面所有元素都得搬）。于是自然会想：能不能定义一种"只许从一端进出"的抽象，把数组这种杂乱用法管起来？ 这正是抽象数据类型（ADT）的动机：从"怎么存"里提炼出"能做什么"。

一、先别急着写代码：什么是抽象数据类型（ADT）

ADT = 一组数据值 + 一组在这些值上可做的操作（契约），它只规定"你能对我做什么"，不规定内部怎么存。

最熟悉的例子其实天天在用：整数就是 ADT。你知道 +、-、* 怎么用，但从不在乎 CPU 里是用补码还是浮点表示——"加法"这个契约对你永远成立，底下的实现你一概不关心。

抓住 ADT 的两面性：

对客户（使用者）：ADT 是一份承诺——"我能给你 push / pop / peek，且永远后进先出"。客户据此写代码，不碰内部。
对实现者：ADT 是一道最低要求——"你只要做到这些操作、且行为符合契约，内部爱怎么存怎么存"。

本质一句话（提前剧透）：ADT 是 what（承诺能做什么），数据结构是 how（怎么存、怎么算）。把两者分开，代码才能被替换、被测试、被信任。

二、ADT ≠ 数据结构：最容易混的一层

这是全篇最该掰清的点。

数据结构（Data Structure） = 数据在内存里真实的排布 + 操作对应的具体算法。数组、LinkedList、哈希桶……都是数据结构。
抽象数据类型（ADT） = 一组操作的契约，与内存排布无关。

同一个 ADT，可以有无数种数据结构实现。拿 Stack 举例：

ADT Stack：操作是 push / pop / peek / isEmpty，语义是 LIFO（后进先出）。这就是全部契约。
实现 A：用数组存，top 指针指向栈顶之上。
实现 B：用链表存，每个节点指向下一个。

两者都满足同一个 ADT，但底层天差地别。下面这张图是整套课要反复回看的关系：

图注：一个 ADT（承诺做什么），多种数据结构（怎么做的）。客户只认 ADT，不认底下是谁——换成链表实现，客户代码一行都不用改。

三、用 Java 把 Stack 的两种实现写出来

CS61B 用 Java。我们先定义一个接口来表达 ADT 契约，再给两种实现。

// ADT 契约：只说能做什么，不说怎么存
public interface IntStack {
    void push(int x);   // 压入
    int pop();          // 弹出栈顶
    int peek();         // 看栈顶但不弹出
    boolean isEmpty();  // 是否为空
}

实现 A —— 数组版 ArrayStack：

public class ArrayStack implements IntStack {
    private int[] a;
    private int size; // 指向下一个可写入的位置（即栈顶之上）

    public ArrayStack(int cap) {
        a = new int[cap];
        size = 0;
    }
    public void push(int x) {
        if (size == a.length) throw new IllegalStateException("栈满");
        a[size++] = x;
    }
    public int pop() {
        if (isEmpty()) throw new IllegalStateException("栈空");
        return a[--size];          // 先退格再取值
    }
    public int peek() {
        if (isEmpty()) throw new IllegalStateException("栈空");
        return a[size - 1];
    }
    public boolean isEmpty() {
        return size == 0;
    }
}

实现 B —— 链表版 LinkedStack：

public class LinkedStack implements IntStack {
    private static class Node {    // 私有嵌套类，外部看不到节点结构
        int val;
        Node next;
        Node(int v, Node n) { val = v; next = n; }
    }
    private Node top;              // 指向栈顶节点

    public void push(int x) { top = new Node(x, top); }
    public int pop() {
        if (isEmpty()) throw new IllegalStateException("栈空");
        int v = top.val;
        top = top.next;            // 栈顶下移
        return v;
    }
    public int peek() {
        if (isEmpty()) throw new IllegalStateException("栈空");
        return top.val;
    }
    public boolean isEmpty() { return top == null; }
}

客户代码——注意它完全不关心底下是谁：

IntStack s = new ArrayStack(10);  // 换成 new LinkedStack() 毫无影响
s.push(1);
s.push(2);
System.out.println(s.pop());     // 2
System.out.println(s.peek());    // 1

输出：

1
2

2
1

这就是 ADT 的回报：把 ArrayStack 换成 LinkedStack，客户那几行代码一个字都不用改——因为契约没变。

四、坑：把"实现"泄露给"客户"

ADT 最大的敌人叫 representation exposure（表示暴露）：实现细节从"后门"溜到客户手里，客户于是能绕过契约直接戳数据。

把上面的 ArrayStack 改成 public 字段试试：

public class ArrayStack implements IntStack {
    public int[] a;     // 灾难：public
    public int size;    // 灾难：public
    // ...
}

客户现在能干这种事：

ArrayStack s = new ArrayStack(10);
s.push(1); s.push(2);
s.a[0] = 999;          // 直接改了"栈底"
s.size = 100;          // 把栈顶指针搅乱

LIFO 契约瞬间破产——客户可以往栈底塞东西、可以伪造栈大小。封装（把所有字段设 private，只通过方法进出）就是为堵这个洞。

第二个更隐蔽的坑：哪怕字段是 private，如果你把内部可变对象的引用返回出去（return a; 或返回内部的 List），客户照样能隔着引用改内部——封装的是"字段可见性"，挡不住"引用逃逸"。这叫"返回可变内部状态的引用"，以后写带容器的类要格外小心。

五、面向对象如何落地 ADT：封装、不变式、别名

Java 用类把"数据 + 操作"捆在一起，用 private 隐藏内部表示，这就是面向对象落地 ADT 的标准姿势。但光封装不够，还要引入一个 CS61B 会反复强调的概念——不变式（invariant）：

不变式 = 对象在「任何方法调用前」和「任何方法调用后」都必须为真的性质。

以 ArrayStack 为例，它的不变式至少包括：

0 ≤ size ≤ a.length；
isEmpty() 为真 当且仅当 size == 0；
a[0..size-1] 里恰好是按压入顺序摆放的栈元素。

每个方法都肩负一个责任：进入时假设不变式已成立，退出时必须让不变式再次成立。pop() 在 size==0 时抛异常，正是为了"不让栈空时还去破坏不变式"。

坑：别名（aliasing）。 Java 的对象是引用语义——Stack b = a; 不是复制，而是让 a、b 指向同一个对象。两个"客户"共享一个栈，会互相干扰：

IntStack a = new ArrayStack(10);
IntStack b = a;          // 没有复制，只是多了一个别名
a.push(7);
System.out.println(b.peek());  // 7 —— b 也被改了

这与"值语义"（如 int）完全不同，是 Java 初学者最容易栽跟头的地方之一。它引出一个重要的工程手段——防御性拷贝（defensive copy）：当方法接收或返回可变对象时，先复制一份再操作，切断别名链路。这里先建立概念，具体写法留到后面带容器的数据结构再展开。

六、如果用 C 语言，ADT 长什么样？

Java 有 class/interface 天然承载 ADT。而在 C 里没有类，ADT 靠 struct + 一组函数 + 头文件约定来实现——接口与实现的分离完全靠"你只用我声明好的函数"这条君子协定：

// stack.h —— 只暴露"能做什么"（ADT 契约）
typedef struct Stack Stack;          // 不透明指针，客户看不到内部
Stack* stack_create(int cap);
void   stack_push(Stack* s, int x);
int    stack_pop(Stack* s);
int    stack_peek(Stack* s);
int    stack_is_empty(Stack* s);

// stack.c —— 怎么存、怎么算，客户一无所知
struct Stack { int* a; int size; int cap; };
// ... 函数实现 ...

struct Stack 在头文件里是不透明的（只 forward-declare），客户永远拿不到字段，被迫只调用那几个函数——这正是 ADT 契约的"C 语言版 enforcement"。对照之下你会更明白：Java 用 private 在语法层面强制封装，C 用"信息隐藏 + 约定"在纪律层面达成同一目标。

七、真实类库里的 ADT 与 DS：光谱模型

上面我们拿自己定义的 IntStack/ArrayStack 讲清了分离。但你在真实 Java 里一上手就会犯懵：ArrayList 明明也是个 class、有方法、能 add/get，它到底是 ADT 还是 DS？List 这个接口，又算什么？

把标准库摊开，先给一张"身份证"表：

名字	是什么	理由
`List`（接口）	ADT	只定契约（有序、可重复、按下标访问），没钉死实现；可换底层
`ArrayList`（类）	数据结构	动态数组实现，名字就暴露了；契约还偷偷承诺了"随机访问 O(1)"
`LinkedList`（类）	数据结构	链表实现
`String`（类）	ADT	只承诺"字符序列的行为"，没承诺底层怎么存

注意 String 这条——它明明是具体类（不是接口），却仍是 ADT。铁证在 Java 9：JDK 把 String 的内部表示从 char[]（UTF-16，每字符 2 字节）换成了 byte[] + coder（Latin-1 时每字符 1 字节，省一半内存），对外 API 一个字没动、行为完全一致：

// Java 8 内部：private final char[] value;
// Java 9 内部：private final byte[] value; private final byte coder;
// 客户代码：十年不变
String s = "hello";
System.out.println(s.length());   // 5，两种实现都返回 5
System.out.println(s.charAt(1));  // 'e'

你能"换底层而客户无感知"，这就是 ADT 的教科书现场。

到这里要修正一个常见误解：ADT 和 DS 不是给对象贴的"二分标签"，而是"契约把实现钉多死"的光谱。

光谱上从左到右：

List 接口：契约零承诺实现 → 最纯的 ADT；
String：契约只承诺"字符序列的行为"，没承诺底层 → 仍是 ADT（尽管它是具体类）；
ArrayList：契约偷偷承诺了"随机访问 O(1)、数组式连续存储" → 已经掉到 DS；
ArrayStack/LinkedStack：名字就写着实现 → DS。

关键差别不在"内部表现能不能改"（其实都能改，只要你重写），而在契约本身有没有把实现/性能画像钉进去。ArrayList 之死，死在它名字和契约都明说了"我是数组版"；String 和 List 没说，所以是 ADT。

这个区分也不是语言强制的，而是设计纪律：Java 用 interface 给你一个干净的切分点，但你可以不守——写个 class OrderService 既定了"能下单"又写死了"用 MySQL 存"，它就既不纯 ADT 也不纯 DS，就是个耦合类。所以"分离"是我们主动选择的能力，不是自动发生的。

本质一句话：判断 ADT 还是 DS，看契约有没有把内部表示钉死——只要客户能换底层而行为不变，就是 ADT 那一层；一旦客户被迫依赖"它底层是数组"这个事实，就掉进 DS。

八、你该带着哪三个问题读每一篇

这篇是 CS61B 整条线的地基，不堆具体算法，只交给你一套贯穿始终的读法。以后碰到任何一种数据结构，都先问自己三件事：

它的 ADT 契约是什么？（能做什么、语义约束是什么）
它用什么数据结构实现？（内存怎么排、操作怎么算）
各操作的时间 / 空间代价如何？（为什么这样实现、代价换来了什么）

把这三问答清楚，一个数据结构就真正"吃透"了，而不是只记住了几个 API。

🐾 小结

ADT = 契约（what），数据结构 = 实现（how）；同一 ADT 可有多种实现，客户只依赖 ADT。
数组是"裸"的数据结构，ADT 是在它之上管住用法的抽象。
表示暴露是头号天敌：字段 private + 只通过方法进出，且别把内部可变引用泄露出去。
封装之外还要守不变式：每个方法进出都须让对象保持"健康状态"。
Java 是引用语义，别名会让多个变量指向同一对象，引出防御性拷贝的需求。
没有 class 的语言（如 C）靠 struct + 不透明指针 + 约定同样能落地 ADT。