1.1 ADT 操作：stack、queue 與 function pointer

動機

在 CSCI2520 中，最常見的問題往往不是少寫一個分號，而是欠缺清楚的 操作契約。

ADT 必須先說明四件事：

• 允許執行哪些操作，
• 每個操作保證甚麼結果，
• 客戶端呼叫後可以依賴甚麼狀態，
• 空結構與錯誤情況如何處理。

最後一項也是正確性的一部分。前置條件描述操作前必須成立的事實； 後置條件描述操作的回傳值與完成後的抽象狀態。若前置條件可能不成立， 介面亦必須規定可觀察的失敗策略。

這項分隔十分重要，因為同一個 stack 或 queue 介面可以由固定陣列、 動態陣列或鏈結串列實作。內部表示改變時，客戶端程式不應隨之改寫。

抽象狀態與失敗原子性

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

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

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

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

stack 的核心不是「一疊物件」這個比喻，而是只能由頂端存取的不變量。

以上是概念層面的操作。下方的課堂 header 並未公開 top；Tutorial 2 則把相應觀察操作稱為 Peek。採用哪一種均可，但公開介面必須前後一致。

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 介面會隱藏內部表示

課堂採用以下不透明型別形式：

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 的指標；客戶端可以傳遞 stack，卻不能直接存取其內部欄位。

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

表示不變量與成本模型

固定陣列把具體的有效 prefix 對應到抽象序列，並保持 count 不超過容量。 動態陣列另須保證配置足以容納容量以下的每個位置。linked stack 則要求 一條無環鏈，首節點表示抽象頂端；若另存 count，它必須等於可到達節點數。 固定陣列的 push 與 pop 是常數時間，但受容量限制。動態增長偶爾要複製 整個目前序列。鏈結操作不作整批複製，卻要配置或釋放節點，而且 locality 不同。這些成本差異不會改變 LIFO 行為。

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

動態陣列在相同 prefix relation 之外再加入容量關係。空 dynamic stack 可以 擁有小型配置，也可以採用 null pointer 配合零容量，但選定 convention 後 必須一致表示。增長改變儲存身份，而不改變元素次序。linked stack 使用 另一 simulation relation：由 top 沿 next link 行走，所得次序是由底至頂 抽象序列的反向。push 安裝一個新 head；pop 拆下一個舊 head。若另存 depth， 每次成功 link 變更都必須在同一次 commit 更新它；若以遍歷計算 depth， 成本便是線性而非常數。兩種選擇仍可滿足完全相同的 observer 後置條件。

Stack 實作方式

課堂投影片強調三個重要概念。

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

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

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

第二，動態陣列版本加入 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 都不可提交新容量或丟失舊配置。

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

Stack 應用：逆波蘭表示法

以下來源例子是 stack 應用，不是 function pointer dispatch table。逆波蘭 表示法先出現 operand，然後才出現 operator，因此程式先 pop 右 operand， 再 pop 左 operand。

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 與除以零。

Queue 雖然相似，但語義不同

Queue 的規則是 FIFO：先入先出。

以由 head 至 tail 的序列表示抽象狀態。Enqueue(Q, x) 的後置條件是 Q' = Q · x。Dequeue(Q) 要求 Q != []；若 Q = x · R，則回傳 x 並令 Q' = R。概念操作 front 與 top 一樣，並未出現在下方較小的 課堂 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 都遵守 相同語義。

定理 / 命題

證明思路

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

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

tutorial 投影片列出以下版本。

• 非循環固定陣列要麼在移除時搬移元素，要麼最終在 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 指標，只要記憶體配置成功即可增長。

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

當容量為正時，循環表示把每個邏輯 rank 加到 front index，再對容量取模， 從而得到儲存位置。enqueue 只改變下一個空位與 count；dequeue 只改變 front index 與 count。每個保留元素的邏輯 rank 因而仍對應到同一個已儲存 值，無須移動該值。在此表示中，另存 count 是 index 重合時區分空與滿的 選定方法；其他有效設計亦可預留一個位置或另存 full flag。動態循環 queue 增長時可以把邏輯序列一次複製到較大區塊，但必須在複製成功後才公開新 區塊與新 index。

考慮容量為五、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。

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

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

其邊界狀態轉移也是表示不變量的一部分：

• 空 queue 同時滿足 head == NULL 與 tail == NULL，
• 對空 queue enqueue 時，兩個指標都指向新節點，
• 對非空 queue enqueue 時，先連接舊 tail，再推進 tail，
• 多節點 queue dequeue 後只推進 head，
• 唯一節點被 dequeue 並釋放後，head 與 tail 都必須重設為 NULL，
• QueueIsEmpty() 只要檢查 head == NULL。

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

鏈結轉移次序與 queue 長度

鏈結更新必須有適當次序，使每個中間狀態都始終由 queue 持有並保持可達。enqueue 先配置並初始化節點，然後才改變任何 queue pointer。dequeue 先保存舊 head 及其值，再推進 head；若 queue 變空便重設 tail，最後才釋放舊節點。同一 次序可一致處理空、單節點與多節點情況，不會留下 dangling public state。 遍歷計算長度無須額外欄位，但時間與可到達節點數成正比。另存 count 可令 observer 成為常數時間，前提是每次成功的 enqueue、dequeue 與 clear 都在 同一次提交轉移中更新它。

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

Function pointer 支援 callback 與真正的分派

function pointer 讓 C 在執行時選擇行為，同時保留可檢查的函數簽名。

最基本而言，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);

課堂以 hashtable 示範 callback traversal operation。

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 契約規定。

函數簽名相容涵蓋每個 parameter 與 return type；cast 不能修復不相容呼叫。 多種 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 語義。

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

用程式測試 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。

常見錯誤

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

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

快速檢查

練習

總結

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