1.1 ADT 操作：stack、queue 與 function pointer

同一介面，不同表示

Stack 可以用陣列，也可以用 linked node 儲存元素。成功執行 push(10) 與 push(20) 後，呼叫者在兩種表示下都應從 pop() 得到 20。陣列索引與 節點地址不同，可觀察的序列卻相同。若呼叫者直接讀取內部 count 欄位 或跟隨 node link，即使 stack 的行為仍然正確，更換表示也可能破壞客戶端。

抽象資料型別把這種可觀察行為與實際儲存分開。前置條件說明何時容許操作， 後置條件說明返回結果和操作後的狀態。失敗行為同樣可見：定長 stack 拒絕 一次 push，而可增長 stack 接受它，除非共享契約明確處理這個差別，否則 不能把兩者視為相同實作。

抽象狀態與失敗原子性

抽象狀態是客戶端所見的數學值，例如由已儲存元素組成的有限序列；陣列 索引、容量與節點地址都不屬於該值。mutator 應先檢查前置條件並取得所需 資源，然後才一次提交表示變更。若操作報告 overflow、underflow 或配置 失敗，失敗原子性要求舊抽象狀態仍可完整觀察。這條規則防止失敗的插入 改變深度或長度，也防止移除操作在報告錯誤前丟失元素。

把程式與抽象狀態精確連接的一種方法，是定義 abstraction function。它把 每個有效的具體表示映射到唯一抽象序列。representation invariant 說明哪些 具體狀態有效；操作契約則說明映射後的序列可以如何改變。兩者必須分開： 客戶端有權依賴操作契約，卻不會看見或修復內部 invariant。另一方面，實作 可在操作期間重新組織儲存，只要中間形式不會外洩，而且最終具體狀態會 映射到承諾的抽象結果。

失敗原子性可以設計成一項短 transaction。首先在不改變狀態的情況下檢查 所有邏輯前置條件；然後計算新容量或 link 值，並拒絕算術 overflow；接着在 舊表示仍完整時取得記憶體或其他資源；最後才把新 pointer、index、count 或 link 作為一次已提交轉移公開。最後階段前的失敗應經已宣告 error channel 返回，令每個 observer 都得到舊答案。即使程式遇錯便終止，這項規律仍使 局部推理更清楚，也支援日後改成可復原介面。

Stack 是只能由頂端操作的結構

Stack 限制下一次移除的對象必須是最近加入的元素。呼叫者不必知道儲存佈局，也能按這個規則預測結果。

以上是概念層面的操作。下方的 C header 並未公開 top；介面也可以把這項 觀察操作命名為 Peek。呼叫者只能使用實際 header 已宣告的操作。

LIFO 是 stack 的基本規則：後入先出。若以由底至頂的序列表示抽象狀態 S，Push(S, x) 的後置條件是 S' = S · x。Pop(S) 的前置條件是 S != []；若 S = T · x，則操作回傳 x，並令 S' = T。

完整的 stack 操作契約

建構操作回傳已初始化、深度為零的空狀態。深度與空狀態測試都是 observer： 它們要求有效的 stack handle，回傳目前序列的資訊，並保持序列不變。 頂端 observer 同樣不改變狀態，但要求序列非空。push 成功後只增加一個 最新元素；pop 只移除該元素。若介面提供 clear，後置條件是序列為空， 並依 ownership policy 釋放表示所擁有的資源。這些語義後置條件都不指定 儲存方式必須是陣列還是節點鏈。

observer 必須冪等且不改變次序；top 不轉移值或 pointee 的 ownership， 相關規則須另寫入契約。push 與 pop 保持其餘元素的次序與值。clear 釋放 表示所擁有的資源後仍留下可重用的空 stack；destructor 才釋放 stack 物件， 並使其後使用無效。

Stack 介面會隱藏內部表示

Opaque handle 防止客戶端依賴內部欄位：

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。客戶端可以保存和傳遞 handle，卻不能 直接存取欄位，因此不同儲存表示可以公開相同宣告。

表示獨立性只保證可觀察行為一致，並不表示成本相同。固定陣列、動態陣列 與鏈結表示可以具有不同的隱藏容量、配置方式與執行時間；但若一項實作 拒絕某次 push，另一項卻接受，該成功或失敗差異便是可觀察的。只有當每次 呼叫結果一致，或共享抽象明確把容量及其失敗策略參數化或排除在外時，它們 才滿足此處的強表示獨立性。複雜度界限只有寫入契約後才可被客戶端依賴。

Stack 實作方式

固定陣列版本以 count 記錄深度：

struct stackCDT {
   stackElementT elements[100];
   int count;
};

其表示不變量是 0 <= count <= 100。只有在 count < 100 時，Push 才可寫入陣列；否則必須先依契約處理 overflow，不可越界寫入。

對固定陣列而言，有效區域恰好是長度等於 count 的 prefix。prefix 以外的 位置可能仍有舊 bits，但它們不是抽象元素，observer 絕不可把它們回傳。 push 在舊 prefix 後第一個位置寫入，並只在寫入合法後增加 count。pop 減少 邏輯長度並回傳原來最後一個 prefix 值；是否清除該位置並不影響語義，因為 縮短後的 count 已把它隱藏。可是在容量已滿時，連第一次寫入都必須等待 overflow policy 選出安全結果後才能發生。

動態陣列版本加入 size，並在滿載時以 realloc() 擴充：

struct stackCDT {
   stackElementT *elements;
   int count;
   int size;
};

此表示必須保持 0 <= count <= size。若 size == 0，亦必須有 count == 0，此時容許 elements == NULL；若 size > 0，elements 必須指向至少可容納 size 個元素的有效儲存空間。Pop() 亦可配合審慎的 縮容策略改善記憶體使用量，而不改變 ADT 介面。

#include <limits.h>
#include <stdint.h>
#include <stdlib.h>

/* StackError 會報告錯誤，而且不會返回。 */
void Push(stackADT stack, stackElementT element) {
   if (stack->count == stack->size) {
      if (stack->size > INT_MAX - 10) {
         StackError("capacity overflow");
      }
      int newSize = stack->size + 10;
      stackElementT *grown;
      if ((size_t)newSize > SIZE_MAX / sizeof *grown) {
         StackError("allocation-size overflow");
      }
      size_t newBytes = (size_t)newSize * sizeof *grown;
      grown = realloc(stack->elements, newBytes);
      if (grown == NULL) {
         StackError("allocation failure");
      }
      stack->elements = grown;
      stack->size = newSize;
   }
   stack->elements[stack->count] = element;
   stack->count++;
}

stackElementT Pop(stackADT stack) {
   if (StackIsEmpty(stack)) {
      StackError("stack underflow");
   }
   return stack->elements[--stack->count];
}

幾何增長如何改變攤銷成本

含有大量元素的 stack 一次 resize 可能很昂貴，因為所有現有值都可能需要 複製。amortized analysis 把偶發成本分攤到此前成本很低的 push。若容量按 幾何比例增長，各次複製大小形成幾何級數，其總和不超過最終深度的常數倍， 所以長操作序列中的平均 push 成本是常數。固定增加容量會觸發更多 resize， 總複製量可達平方量級。這項成本分析與失敗原子性互相獨立：無論採用哪種 增長規則，失敗的 resize 都不可提交新容量或丟失舊配置。

例如，容量按 1, 2, 4, 8, ... 增長時，複製量由之前容量的總和控制， 而這個幾何和小於下一個容量。因此，只含 push 的長序列總複製量是線性的； 觸發 resize 的某一次 push 仍可能花費目前深度的線性時間。攤還界並不表示 每一次操作都同樣快。

縮容需要另一套 policy。每次 pop 後立即收縮，會令交替 push 與 pop 反覆 複製相同的值。較低的 shrink threshold 形成 hysteresis：容量在滿載邊界 增長，但只在使用率顯著降低時收縮。若 shrink allocation 失敗，實作可以 安全保留較大區塊，因為它仍表示所承諾序列。因此，失敗的 growth 會阻止 插入；失敗的可選 shrink 卻不必令本來成功的 pop 失敗。

鏈結表示與不同的成本模型

增長改變儲存身份，而不改變元素次序。Linked stack 要求無環鏈，首節點表示 頂端。它使用 另一 simulation relation：由 top 沿 next link 行走，所得次序是由底至頂 抽象序列的反向。push 安裝一個新 head；pop 拆下一個舊 head。若另存 depth， 每次成功 link 變更都必須在同一次 commit 更新它；若以遍歷計算 depth， 成本便是線性而非常數。兩種選擇仍可滿足完全相同的 observer 後置條件。 合法的固定陣列 push 與 pop 都是常數時間；linked stack 同樣只改變一個節點， 但配置成本與 locality 有別於連續儲存。

錯誤通道與被拒絕的更新

underflow 與 overflow 策略必須在整個介面中一致。終止策略應報告原因， 並在 mutation 前停止；可復原策略應把狀態與元素值分開回傳，使每個可能 元素仍可表示。exception 不是 C 的內建機制，靜默回傳任意值亦不是契約。 對 bounded queue 而言，滿載是預期狀態；對動態結構而言，配置失敗是資源 事件。兩者可以共用報告機制，但都不可讓 counter、index 或 link 只更新 一半。

Sentinel 也可能是合法元素值。把狀態與輸出值分開返回可避免歧義；上面的 不返回處理器則放棄復原。不同操作若混用這些失敗策略，客戶端便無法統一 推理失敗後的行為。

capacity overflow 與 arithmetic overflow 亦須區分。前者表示 representation 沒有獲准使用的空位；後者表示建議的新容量或 byte size 即使尚未要求記憶體， 已無法安全表示。allocation failure 則表示可表示的 request 未能滿足。三者 都應在抽象 append 發生前拒絕 insertion，但 diagnostic 與 recovery choice 可以不同。明確命名這些情況，便可把模糊 error handling 變成可測試的 ADT 契約部分。

Stack 應用：逆波蘭表示法

逆波蘭表示法先出現 operand，再出現 operator。最近壓入的是右 operand， 因此程式先 pop 右 operand，再 pop 左 operand。計算只依賴 stack 契約，無須 存取其內部欄位。

void ApplyOperator(char c, stackADT stack) {
   /* 必須在兩次 Pop 前檢查：depth >= 2；c 合法；所選結果可由 int
      表示；若為除法，y != 0，且 operand pair 不是 INT_MIN, -1。 */
   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;
   }
}

對格式正確的輸入，後置條件是以運算結果取代頂端兩個 operand，而較低位置 的 operand 次序不變。在兩次 pop 之前，呼叫端必須確認所選 +、- 或 * 結果可由 int 表示；除法亦要求除數非零，並拒絕 INT_MIN / -1。 這些檢查同時避免有符號整數 overflow 的 undefined behavior 與除以零。

FIFO 需要在兩端操作

工作隊列需要取出最早仍在等待的項目，即使期間不斷有新項目到達。這個 FIFO 規則要求在相反的邏輯端點執行插入與移除。

以由 head 至 tail 的序列表示抽象狀態。Enqueue(Q, x) 的後置條件是 Q' = Q · x。Dequeue(Q) 要求 Q != []；若 Q = x · R，則回傳 x 並令 Q' = R。概念操作 front 與 top 一樣，並未出現在下方較小的 C header 中。

Queue 的 header 同樣採用不透明形式：

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 操作契約

建構操作回傳空的 head-to-tail 序列。長度與空狀態測試是不改變狀態的 observer，而 front observer 另要求 queue 非空。enqueue 成功後恰好把一個 元素附加於 tail；dequeue 成功後回傳並移除 head。clear 的後置條件是空 序列。overflow、underflow 與配置失敗都必須依已宣告策略處理，不可暴露 部分更新的序列。線性陣列、循環陣列、動態陣列與 linked queue 都遵守 相同語義。

合法更新為何保持 LIFO 與 FIFO

對操作數目作歸納。零次操作時，兩個狀態均為空，命題立即成立。假設命題 在 k 次操作後成立。stack 的 push 把值加到由底至頂序列的右端；合法 pop 只移除該最右端值。queue 的 enqueue 把值加到由 head 至 tail 序列的右端； 合法 dequeue 只移除最左端值。top、front 與 isEmpty 等觀察操作不會 改變序列。因此每一種下一步操作均保持回傳規則與剩餘元素的相對次序， 歸納完成。

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)--];
}

Queue 的實作：array、circular array、linked list

反覆移除首元素會帶來 stack 沒有的儲存問題：空位可能不斷積累在 front 之前。

• 非循環固定陣列要麼在移除時搬移元素，要麼最終在 front 之前留下無法 直接重用的位置；
• 循環陣列把第 i 個邏輯元素存於 (front + i) % capacity。若另存 count，空狀態是 count == 0，滿載是 count == capacity；enqueue 寫入 (front + count) % capacity，dequeue 則以模運算推進 front， 所有保留元素都不需要搬移。執行任何模運算之前，表示不變量必須保證 capacity > 0、0 <= front < capacity 與 0 <= count <= capacity；零容量 dynamic queue 必須先增長；
• 動態循環陣列保持相同邏輯不變量，只在滿載時增長；
• 鏈結串列使用 head 與 tail 指標，只要記憶體配置成功即可增長。

循環儲存為何無須搬移元素

考慮容量為五、front 位於實體位置三、count 為四的 queue。其邏輯元素依次 佔據位置三、四、零與一，下一個空位是二。移除 front 後，front 推進至位置 四，count 減至三；位置四、零與一的值完全不移動。其後一次插入會寫入位置 二。這段 trace 說明實體 index 次序與邏輯 FIFO 次序並不相同，也說明直接 列印 raw array 不是有效的 queue observer。

no-shift 性質對每個容量為正的有效狀態都成立，而不只限於上述例子。移除 前，舊邏輯 rank r + 1 儲存在 (front + (r + 1)) % capacity。front 推進後，該 survivor 的新 rank 為 r，而位置表示式給出相同儲存位置。 因此每個 survivor 已在正確的新邏輯位置。在此選用的 count-based 設計中， count 界定所有邏輯 rank、指出下一個插入位置，並區分空與滿；其他有效的 循環表示可用不同方式承擔這些作用。dynamic growth 時，依 rank 次序把元素 複製到新 prefix，再把新 front 設為零，便會在較大區塊建立相同 invariant。 其他循環設計可以預留一個位置或另存 full flag。新區塊與 index 只能在配置及 複製成功後公開。

struct cellT {
   queueElementT element;
   struct cellT *next;
};

struct queueCDT {
   struct cellT *head;
   struct cellT *tail;
};

空 queue 的表示同時要求 head == NULL 與 tail == NULL，因此 QueueIsEmpty() 可以只檢查 head == NULL。跨越空與單節點的邊界時， 更新必須維持兩個 endpoint 的一致性。

在保存 head 與 tail 的前提下，鏈結 enqueue 與 dequeue 都是常數時間。 這個只存兩端指標的表示以遍歷計算 QueueLength，成本為線性；另存並正確維護 count 可把長度查詢改為常數時間，但亦增加一項表示不變量。

鏈結轉移次序與 queue 長度

新節點必須先配置並初始化，才能改變 queue 的 endpoint。不同邊界狀態決定 接下來需要更新哪些 link。

empty-to-one 轉移沒有舊 tail，因此配置成功後須同時公開兩個 endpoint； 非空插入則先連接舊 tail，再推進 tail。移除時須在節點仍存活時複製 value， 再推進 head；若 successor 為 null，釋放舊節點前亦須把 tail 設為 null。 allocation failure 發生在任何 endpoint 改變前，故 enqueue 保持失敗原子性。 Clear 可以重複安全的節點拆除，或使用等價走訪，最後恢復兩個 null endpoint。 若另存 count，enqueue、dequeue 與 clear 都必須同步更新它，clear 後為零。

Function pointer 支援 callback 與真正的分派

容器可以確定要走訪哪些 entry，卻不必預先決定呼叫者要如何處理它們。 Callback 在執行時提供這項操作，同時保留可檢查的函數簽名。

最基本而言，function pointer 儲存程式碼地址：

int (*fp)(int);

括號把「指向函數的指標」與「回傳指標的函數」區分開來。typedef 可使 契約更容易閱讀：

typedef int (*intToIntFnT)(int);
int square(int x) { return x * x; } /* 此處要求 x * x 可由 int 表示。 */
intToIntFnT fp = square;
int value = fp(3);

Dictionary 可以自行走訪 entry，再讓 callback 處理每個關聯。客戶端無須知道 bucket 的具體佈局，因此可以先獨立訂明這個 traversal 介面。

typedef void (*hashtableFnT)(char *, void *);

/* 前置條件：fp != NULL；key 是借用且唯讀的。 */
void ForEachEntryDo(hashtableFnT fp, hashtableADT table);

void PrintEntry(char *key, void *value) {
   printf("%s\t%d\n", key, *((int *)value));
}

客戶端可以傳入：

void DisplayWordCount(hashtableADT table) {
   ForEachEntryDo(PrintEntry, table);
}

這個模式由實作負責 traversal，由客戶端負責每個 entry 的特定行為。 prototype 會檢查呼叫形狀，但 void * 仍會抹去 payload 型別；PrintEntry 必須恢復並正確使用實際的 pointee 型別。

Command dispatch 應用把指向 cmdEntryT wrapper 的物件指標存為 command 名稱所對應的值；function pointer 位於 wrapper 內，而不是由 hashtable 的物件指標直接充當：

typedef void (*cmdFnT)(void);
typedef struct { cmdFnT fp; } cmdEntryT;

void ExecuteCommand(char *cmd, hashtableADT commands) {
   cmdEntryT *entry = (cmdEntryT *)Lookup(commands, cmd);
   if (entry == NULL || entry->fp == NULL) {
      printf("Undefined command: %s\n", cmd);
      return;
   }
   entry->fp();
}

這才是真正的 function-pointer dispatch：lookup 選出簽名相容的函數， 再經儲存的 pointer 呼叫。前述 RPN switch 並不是 dispatch table。

簽名邊界與 dispatch table 的生命週期

相容性涵蓋完整函數型別：parameter type、return type 與呼叫點使用的 prototype 都必須一致；cast 不能令不相容呼叫變得安全。此處的 ForEachEntryDo 要求 callback 非空，按明確宣告為不指定的次序恰好訪問 每個 entry 一次，並禁止在 traversal 期間改變 table 結構或 key。每個 key 與 payload pointer 都是借用值，除非另有較長生命週期說明，否則只在該次 callback 期間有效。舊式簽名雖然暴露 char *，callback 仍須把 key bytes 視為唯讀，不得保留、釋放或改寫。void * 不提供 run-time type proof， 因此 payload 的實際 object type 與 ownership 必須由周邊 ADT 契約規定。

僅有相同參數個數並不足夠；透過不相容函數型別呼叫具有 undefined behavior。 多種 command shape 必須採用真正共通的 wrapper signature 或分開的 typed table；(void) 表示不接收參數，不同於舊式的未指定 parameter list。

dispatch table 起始於有效的空 registration state。registration 把 command key 與 table 擁有的 cmdEntryT wrapper 關聯；wrapper 內含非空且簽名相容的 function pointer，並依文件所定 replace-or-reject policy 解決 duplicate key。 wrapper 在 entry 被移除或 table 被銷毀前保持有效，函數地址本身不由 table 擁有。目前的 wrapper 沒有 context；若日後加入 context，registration 亦須 規定 table 是否擁有它，以及移除時使用哪個 destructor。execution 對 absent wrapper 或空 entry->fp 都不得間接呼叫，然後只呼叫所選 entry。正是這個 lifecycle 令 table 成為可擴充的 conditional chain 替代方案；單純寫出 switch 並不會產生 registration 與 lookup 語義。

用程式測試 ADT 契約

更換表示後，可以執行同一操作序列，比較介面返回的值與可觀察狀態， 從而檢查行為是否仍然一致。

一個實用方法是撰寫小型 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 應確認第一個入隊的元素仍然最先出隊。測試可要求相同的可觀察行為， 卻不應假設兩種表示具有相同成本。

表示獨立的契約測試矩陣

通用 black-box 測試應檢查空建構、重複 observer、單元素移除、多元素次序， 以及共享的成功與失敗策略。每個被拒操作後，測試再次觀察深度、長度， 並在介面已公開且滿足非空前置條件時觀察 top 或 front，以便在不讀取 欄位的情況下驗證失敗原子性。表示特有測試應另行配置：填滿固定容量實作 來觸發 overflow，以 instrumented allocator 令動態增長失敗，使循環實作跨越 wrap boundary，並讓 linked backend 執行單節點 pointer 轉移。這些案例不能 原樣套用到每一種 backend。複雜度量度亦應另置，因為相同結果不代表相同 配置、遍歷或 resize 成本。只有測試框架刻意使用 operations table 在執行時 選擇實作時，才需要 function pointer。

Model-based test 可以維護一個簡單序列作為 oracle，把相同操作分別施加於 模型與 ADT，並比較返回值及 observer 結果。模型只表達契約，因此不依賴 具體欄位。測試序列應包含空、單元素與多元素之間的轉移。

失敗測試需要可控制的原因，例如填滿有界表示，或讓配置層拒絕下一次申請。 被拒操作後，除了重新檢查 observer，還應繼續執行合法操作，確認物件仍可 使用。Callback 測試記錄被訪問的 entry 與 payload identity；dispatch 測試則 涵蓋已註冊命令、未知 key 及替換策略。時間與配置次數另行量度，不能以速度 代替語義正確性。

常見錯誤

快速檢查

練習

總結

ADT 契約規定合法狀態轉移與失敗行為。stack 與 queue 的實作即使採用不同 儲存方式和成本，也必須保持各自的 LIFO 與 FIFO 序列不變量。function pointer 提供受簽名約束的 callback 與 dispatch，但不能取代帶來表示獨立性的 ADT 介面。