抽象数据类型
Abstract Data Types
约 10 分钟 · v11
抽象数据类型 ADT
cs-c/abstract-data-types · COMP25211 先看：底层偷偷换掉，你用起来没差别
左边是调用方代码——它只会 push / pop / peek，从不碰内部。右边是底层实现，你可以在「数组」和「链表」之间随时切换。点操作按钮，再切换底层：留意——调用方一行都不用改，每个操作的结果也完全一样，变的只是右边内部长什么样。
一个栈（Stack），两种底层
两种底层的 push/pop 都满足同一条规则：后进先出（LIFO）。数组实现靠"末尾 + top 下标"，链表实现靠"头插 + head 指针"——内部完全不同，但对外行为一模一样，所以调用方感知不到换没换。
这就是抽象数据类型（ADT）：它只规定有哪些操作、每个操作的行为（契约），不规定内部怎么存、怎么实现。"栈"是一个 ADT——push/pop/peek + LIFO 规则；用数组还是链表，是实现的自由。
一句话：ADT = 接口（能做什么）与实现（怎么做到）的分离。调用方只依赖接口，不依赖内部。
2 接口 vs 实现：到底分的是什么
把一个数据类型拆成两层看，是 COMP2521 的核心思维。栈这个 ADT 为例：
| 接口（ADT，对外承诺） | 实现 A：数组 | 实现 B：链表 |
|---|---|---|
push(s, x)把 x 放到栈顶 | arr[top++] = x; | 头插一个新节点 |
pop(s)弹出并返回栈顶 | return arr[--top]; | 摘下 head，head=head→next |
peek(s) / isEmpty(s) | arr[top-1] / top==0 | head→item / head==NULL |
| 契约（不变量） | 后进先出；满 / 空时的行为有明确约定。两种实现都必须遵守——否则就不是"栈"。 | |
接口是承诺（操作签名 + 行为契约），写在头文件 Stack.h 里；实现是兑现承诺的方式，藏在 Stack.c 里。调用方 #include "Stack.h" 就够，看不到也不该看到 .c 里的数组或链表。
在 C 里靠"不透明指针"（typedef struct stack *Stack;，结构体定义只在 .c 里）做到这层隐藏——调用方拿到的是个句柄，碰不到字段。
3 这层分离值多少钱
为什么要费劲分两层？因为它买来四样东西——上面那个"换底层不改调用方"的演示，就是第一样的现场证据。
Stack.h 就知道怎么用，不必读实现。你已经天天在用 ADT 而不自知：C 的 FILE *（fopen/fread/fclose，你从不碰它内部）、各种语言的 List / Map / Set——都是"接口稳定、实现可换"的 ADT。
4 自测
三道题，点选项即时判对错。
一句话带走：
ADT = 接口与实现分离。接口规定"有哪些操作 + 行为契约"（如栈的 push/pop/peek + LIFO），实现规定"内部怎么存"（数组 or 链表）。调用方只依赖接口、碰不到内部——于是换实现不改调用方、能独立测试、复杂度被隐藏、接口即文档。COMP2521 里几乎每个数据结构（栈、队列、列表、集合、优先队列）都是先定 ADT 再选实现——"先想清楚要什么操作，再决定怎么存"，这就是这门课的思维主线。