為甚麼先講契約
在 CSCI2520 入面，最常見的錯誤通常唔係少咗一個分號，而係少咗一個 清楚嘅契約。
ADT 會先講清楚四件事：
- 允許做咩操作，
- 每個操作要保證咩結果，
- client 呼叫之後可以假設咩狀態，
- 空結構同錯誤情況點處理。
呢個分隔好重要，因為同一個 stack 或 queue 介面，可以用 fixed array、 dynamic array，或者 linked list 去做。client code 唔應該因為內部實作改 咗，就要一齊改。
定義
ADT 契約與實作
ADT 契約描述操作同語義。 實作就決定資料欄位、記憶體布局，以及更新方式。 契約係承諾；實作係機制。
Stack 係一個只可以由頂端操作嘅結構
講到 stack，最核心唔係「一疊嘢」呢個比喻，而係 top-only 呢條不變量。
定義
Stack 核心操作
對一個 stack ：
push(x)：將x放入頂端，pop()：移除並回傳頂端元素，top()：睇頂端但唔移除，isEmpty()：檢查有冇元素，StackDepth()：回傳深度。
LIFO 係 stack 嘅基本規則：後入先出。
例題
追蹤 stack 狀態
初始係空 stack。
push(10)之後係[10]push(20)之後係[10, 20]top()回傳20，狀態唔變pop()回傳20，stack 變成[10]
Stack 介面會隱藏內部表示
課堂入面用到嘅 opaque type 形式係：
typedef struct stackCDT *stackADT;
typedef int stackElementT;
stackADT EmptyStack(void);
void Push(stackADT stack, stackElementT element);
stackElementT Pop(stackADT stack);
int StackDepth(stackADT stack);
int StackIsEmpty(stackADT stack);
呢個設計唔係修飾，而係保護契約。stackADT 只係指向唔完整
struct 嘅指標，client 可以傳遞 stack，但唔可以直接入去改內部欄位。
定理
表示獨立性
如果 client 只可以透過 ADT 已宣告嘅操作去用個資料結構，咁 internal representation 就可以自由更改，而唔影響 client 可見行為。
Stack 實作方式
slides 入面強調咗三個重要概念。
第一，fixed array 版本會用一個 count 去記錄深度：
struct stackCDT {
stackElementT elements[100];
int count;
};
呢個版本簡單，但最大深度固定係 100。當深度超過上限，就會出現 representation-level 嘅 overflow。
第二，dynamic array 版本會再加 size，同埋喺滿咗之後用 realloc() 扩充：
struct stackCDT {
stackElementT *elements;
int count;
int size;
};
第三，Pop() 仲可以進一步收斂 memory usage，令實作更完整。意思係：
ADT 介面唔變，但 memory policy 可以一步一步改善。
例題
Push / Pop 的簡化實作
void Push(stackADT stack, stackElementT element) {
if (stack->count == stack->size) {
stack->size += 10;
stack->elements = realloc(
stack->elements,
stack->size * sizeof(stackElementT)
);
}
stack->elements[stack->count] = element;
stack->count++;
}
stackElementT Pop(stackADT stack) {
stack->count--;
return stack->elements[stack->count];
}
重點係：
count代表下一個可用位置，push先存再加一，pop先減一再回傳舊頂端。
Queue 雖然似，但語義完全唔同
Queue 嘅規則係 FIFO：先入先出。
定義
Queue 核心操作
對一個 queue ：
enqueue(x)：由尾端加入x，dequeue()：由前端移除並回傳，front()：睇前端但唔移除，isEmpty()：檢查有冇元素，QueueLength()：回傳長度。
Queue 的 header 都係 opaque 形式：
typedef struct queueCDT *queueADT;
typedef int queueElementT;
queueADT EmptyQueue(void);
void Enqueue(queueADT queue, queueElementT element);
queueElementT Dequeue(queueADT queue);
int QueueLength(queueADT queue);
int QueueIsEmpty(queueADT queue);
Queue 的實作：array、circular array、linked list
tutorial slide 已經清楚指出幾個版本。
- fixed array 版本最易明白，但前端出咗位之後會浪費空間；
- circular array 透過 modulus
%wrap around，令前後位置可以重用； - linked list 用
head同tail指標，增減元素時唔需要搬移舊資料。
struct cellT {
queueElementT element;
struct cellT *next;
};
struct queueCDT {
struct cellT *head;
struct cellT *tail;
};
linked list 版本嘅意思係：
- 新節點接去尾端，
head指向前端，QueueIsEmpty()只要檢查 。
例題
點解 circular array 比 plain array 好
如果 queue 不斷交替 enqueue 同 dequeue：
- plain array 會喺前端釋放咗空位之後，未必有效重用；
- circular array 會將
front同rearwrap around，將前面空間重新用返。
所以 tutorial 先會問你：如果重複做幾百萬次 enqueue / dequeue，會發生咩事？
function pointer 令 C 可以做分派同 callback
function pointer 唔係額外技巧，而係 C 做 runtime dispatch 嘅核心工具。
int (*fp)(int);
呢個宣告表示 fp 係一個指向「接收一個 int，回傳一個 int」函數嘅
指標。prototype 就係 type contract。
定義
Function pointer 規則
function pointer 只可以指向參數列表同回傳型別都相符嘅函數。
課堂入面用 hashtable 做咗一個好實際嘅例子：加一個 callback traversal operation。
typedef void (*hashtableFnT)(char *, void *);
void ForEachEntryDo(hashtableFnT fp, hashtableADT table);
client 可以傳入：
void DisplayWordCount(hashtableADT table) {
ForEachEntryDo(PrintEntry, table);
}
呢個模式對 ADT 好有用，因為 traversal 交畀 implementation 做，而每個 entry 要點處理，就由 client 提供。
同樣，dispatch table 都可以靠 function pointer 去做，避免一大串 if
判斷。
void ApplyOperator(char c, stackADT stack) {
int y = Pop(stack);
int x = Pop(stack);
switch (c) {
case '+': Push(stack, x + y); break;
case '-': Push(stack, x - y); break;
case '*': Push(stack, x * y); break;
case '/': Push(stack, x / y); break;
}
}
呢個例子入面，stack 用嚟存 operand，而 operation table 決定點樣 combine 佢哋。function pointer 令 C 有咗一種手動控制嘅 polymorphism。
邊讀邊試
追蹤 ADT 操作語義
這個工具現在把 C 風格程式範例和可編輯指令串列放在一起，讓讀者可以直接測試 stack 與 queue 的 ADT 語義。
程式範例
typedef struct {
int data[100];
int top;
} Stack;
void push(Stack *s, int x) {
s->data[++(s->top)] = x;
}
int pop(Stack *s) {
return s->data[(s->top)--];
}自己試一試
行變換: push(10)
stack: [10]
queue: []
頂端現為 10。
自己試一試
push 10
目前狀態: [10]
回傳值: 沒有回傳值
push 20
目前狀態: [10, 20]
回傳值: 沒有回傳值
top
目前狀態: [10, 20]
回傳值: 20
pop
目前狀態: [10]
回傳值: 20
push 7
目前狀態: [10, 7]
回傳值: 沒有回傳值
最後狀態: [10, 7]
用程式測試 ADT 契約
當介面固定之後，下一個問題唔應該只係「可唔可以 compile」，而係 「每一步可觀察到嘅狀態轉移，係咪仍然符合契約」。
一個實用做法係寫細型 trace test：
stackADT s = EmptyStack();
Push(s, 10);
Push(s, 20);
assert(StackDepth(s) == 2);
assert(Pop(s) == 20);
assert(Pop(s) == 10);
assert(StackIsEmpty(s));
呢類測試有價值，因為佢檢查嘅係 ADT 層次嘅承諾，而唔係底層記憶體布局。 就算之後你將 array-based stack 換成 linked representation，只要契約冇變， 同一組測試都應該原封不動咁通過。
queue 都一樣：一段短短嘅 enqueue、enqueue、dequeue、dequeue
trace，就應該證明第一個入隊嘅元素仍然係第一個出隊。
常見錯誤
常見錯誤
將 stack 同 queue 語義混淆
push / pop 係 stack；enqueue / dequeue 係 queue。改名唔改行為，
就係破壞 ADT 契約。
常見錯誤
忽略空結構錯誤策略
空 stack 做 pop、空 queue 做 dequeue，都一定要預先定義清楚錯誤處理。
常見錯誤
把介面穩定同實作穩定混為一談
應該保持穩定嘅係介面；應該可以演進嘅係內部 representation。
快速檢查
快速檢查
做完 push(1), push(2), pop() 之後，stack 仲剩低咩？
按 LIFO 去判斷。
解答
答案
快速檢查
做完 enqueue(4), enqueue(7), dequeue() 之後，回傳咩元素？
按 FIFO 去判斷。
解答
答案
快速檢查
點解 ForEachEntryDo(PrintEntry, table) 需要 callback type，而唔係普通 generic pointer？
重點係 type checking 同 parameter list 配對。
解答
引導答案
練習
快速檢查
寫出 Pop(stack) 對非空 stack 嘅前置條件同後置條件。
盡量精確。
解答
引導答案
快速檢查
解釋點解 linked list queue 可以 enqueue 而唔需要搬移舊元素。
用 head 同 tail 去講。
解答
引導答案
快速檢查
用一小段文字解釋 function pointer 點樣幫 ADT 測試。
要講到介面同實作分離。
解答
引導答案
重點總結
真正重要嘅唔係「stack 同 queue 係兩種資料結構」咁簡單，而係：
- ADT 契約定義行為，
- 實作負責存取同記憶體，
- function pointer 令 C 可以維持 type-safe 嘅分派同 callback。