冒號和他的學生們（連載 23）——數據抽象：從隊列 ADT 看接口與實現的分離

第 23 課以 C 語言實現隊列 ADT 為載體，證明抽象數據類型（ADT）非 OOP 專利。通過「循環數組」與「鏈表」兩種截然不同的實現對比同一接口，生動展示數據抽象的核心價值：接口穩定、實現可替換、開發時空分離、人員分離。並澄清 ADT 與數據結構、具體類型、OOP 類的關係。

核心概念辨析

ADT = 接口（契約）+ 實現（隱藏）。具體類型 = 透明數據容器。

隊列 ADT 接口定義 (C 風格)

typedef char ItemType;
typedef struct QueueType* Queue;

int queue_initialize(Queue);
void queue_finalize(Queue);
int queue_add(Queue, ItemType);
int queue_remove(Queue, ItemType*);
int queue_empty(Queue);
int queue_length(Queue);
int queue_head(Queue, ItemType*);

用戶只見接口，不知 QueueType 內部結構——這就是數據抽象。

兩種實現對比

1. 循環數組實現

• 結構：data[]、first、last、count、size
• 特點：自動擴容 (queue_resize)、隨機訪問快、緩存友好

2. 鏈表實現

• 結構：head、tail、count + 節點 item、next
• 特點：動態分配、無擴容開銷、插刪 O(1)

客戶代碼完全相同，無感知切換實現。

關鍵價值

1. 開發時間分離：接口定稿後，實現可延遲決策，並行開發。
2. 開發人員分離：維護不限於原作者，接口文檔即傳遞契約。 3. 非 OOP 語言也能做 ADT：C 用文件作模塊、static 隱藏內部函數、規范自律替代語法強制。

OOP 中的類與 ADT 關係

• 類 = 帶繼承多態的 ADT
1. 非所有類都是 ADT（如 DTO/VO 為具體類型） 2. C# 區分 class (引用類型/ADT) 與 struct (值類型/具體類型) 3. C++ class/struct 機制同，約定俗成前者做 ADT 4. Java 無值類型，全部 class；C 無類只有 struct

句號總結的 ADT 三要素

「抽象——接口與實現相分離；數據——以數據為中心組織邏輯；類型——單純而定義良好的概念。」

本章啟示

數據抽象是 OOP 的起源與核心。沒有 ADT 思維，封裝/繼承/多態皆成無本之木。設計「萬人迷」類的三要素：優雅外形（抽象）、豐富內涵（數據）、鮮明個性（類型）。