Lecture 06A（下）：介面與抽象資料型別

介面就是契約

上一節的 第一行寫著 。 長這樣：

public interface Account {
    /** 存入 amount。前置條件：amount >= 0 */
    void deposit(int amount);

    /** 提出 amount。前置條件：0 <= amount <= getBalance() */
    void withdraw(int amount);

    /** @return 目前餘額，後置條件：回傳值 >= 0 */
    int getBalance();
}

幾條語法規則：

• 介面裡的方法自動是 且抽象的（沒有本體，以分號結尾），不必也不該再寫 。

• 實作類別的方法必須是 ，並建議加上 —— 這個標註讓編譯器幫你檢查「我真的在實作介面的方法」，拼錯名字時會立刻報錯，而不是默默變成一個無關的新方法。

• 介面不能被 ： 是編譯錯誤，因為它沒有任何實作。

• 一個類別可以同時實作多個介面：。

為什麼要多這一層？——解耦

裡有一個只認識 的函式：

static void handleAccount(Account a) {      // 參數型別是介面，不是某個具體類別
    System.out.println("  餘額：" + a.getBalance());
    a.deposit(500);
    System.out.println("  存入 500 後：" + a.getBalance());
}

於是 與 都合法， 而 的內部長得完全不一樣（它有 欄位、開戶送 10000 點、每次存入加送 1%）。 執行結果：

BankAccount：
  餘額：0
  存入 500 後：500
 PointsAccount：
  餘額：10000
  存入 500 後：10505

抽象資料型別

案例：聊天紀錄的兩種實作

考慮聊天室要保存的訊息紀錄。它的 ADT 非常簡單：

public interface ChatHistory {
    void addMessage(String msg);   // 新增一則訊息
    void display();                // 最新在前，逐行印出
    int size();                    // 目前保存的訊息數量
}

同一份契約，我們寫出兩種截然不同的資料結構。

實作一：環狀緩衝區

固定容量的陣列，滿了以後新訊息覆蓋最舊的那一則。索引用 取餘數「繞回」開頭， 所以叫。

private final String[] arr;      // 固定大小
private int nextAvailable;       // 下一則要寫入的索引
private int size;                // 目前保存的數量（<= arr.length）

@Override
public void addMessage(String msg) {
    this.arr[this.nextAvailable] = msg;
    this.nextAvailable = (this.nextAvailable + 1) % this.arr.length;   // 繞回
    if (this.size < this.arr.length) {
        this.size = this.size + 1;   // 還沒滿才 +1；滿了就是覆蓋
    }
}

@Override
public void display() {
    int idx = (this.nextAvailable - 1 + this.arr.length) % this.arr.length;  // 最新
    for (int i = 0; i < this.size; i++) {
        System.out.println(this.arr[idx]);
        idx = (idx - 1 + this.arr.length) % this.arr.length;   // 往回退一格
    }
}

實作二：鏈結串列

不限數量、永不覆蓋。新訊息永遠接在最前面（prepend），所以串列天生就是「最新在前」的順序。

public class LinkedListChatHistory implements ErasableChatHistory {

    private static class Node {          // 靜態巢狀類別：外界看不到
        final String msg;
        final Node rest;
        Node(String msg, Node rest) { this.msg = msg; this.rest = rest; }
    }

    private Node head = null;            // null 代表空串列
    private int size = 0;

    @Override
    public void addMessage(String msg) {
        this.head = new Node(msg, this.head);   // 新節點指向舊 head，再成為新 head
        this.size = this.size + 1;
    }

    @Override
    public void display() {
        Node current = this.head;
        while (current != null) {
            System.out.println(current.msg);
            current = current.rest;
        }
    }

    @Override public int size() { return this.size; }
    @Override public void erase() { this.head = null; this.size = 0; }
}

同一段程式碼，兩種實作

static void simulateChat(ChatHistory history) {   // 只認識 ChatHistory
    history.addMessage("Alice: 嗨！");
    history.addMessage("Bob: 你好～");
    history.addMessage("Alice: 週六要一起讀 Java 嗎？");
    history.addMessage("Bob: 好啊，下午兩點圖書館見。");
    System.out.println("  （共 " + history.size() + " 則，最新在前）");
    history.display();
}
simulateChat(new LinkedListChatHistory());        // 4 則全留
simulateChat(new CircularBufferChatHistory(3));   // 只留最近 3 則

宣告型別決定你能呼叫什麼

實作的其實是 ——一個擴充了 的介面：

public interface ErasableChatHistory extends ChatHistory {
    void erase();          // 在 ChatHistory 的三個方法之外，再多要求一個
}

於是同一個物件，用不同型別的變數接住，能呼叫的方法就不同：

ChatHistory h1 = new LinkedListChatHistory();
h1.addMessage("hello");
// h1.erase();   // 編譯錯誤！h1 的「宣告型別」是 ChatHistory，契約裡沒有 erase()

ErasableChatHistory h2 = new LinkedListChatHistory();
h2.erase();      // OK

最經典的 ADT：List

是「有順序、允許重複、大小可變」的集合——最後一點正是它與陣列的根本差別。 一個最小的 List ADT：

public interface SimpleList {
    int size();
    Object get(int index);   // 前置條件：0 <= index < size()
    void add(Object o);      // 加到尾端；後置條件：size() 增加 1
    void remove(Object o);   // 移除第一個 equals(o) 的元素；不存在則不動作
}

元素型別暫時用 （Java 裡所有物件的共同祖先，所以什麼都能放）； 第 [sec:generics] 節會用泛型把它升級成 ，讓編譯器幫我們記住裡面放的是什麼。

用鏈結串列實作它。這裡的重點不是演算法，而是封裝把「使用串列」變得多簡單： 使用者不必知道 的存在，不必自己區分「空串列」與「非空串列」，不必記得維護 。

@Override
public void remove(Object o) {
    if (this.head == null) return;                      // 空串列
    if (Objects.equals(this.head.value, o)) {           // 移除的是第一個節點
        this.head = this.head.next;
        this.size = this.size - 1;
        return;
    }
    Node prev = this.head;
    while (prev.next != null) {
        if (Objects.equals(prev.next.value, o)) {
            prev.next = prev.next.next;                 // 跳過被移除的節點
            this.size = this.size - 1;
            return;
        }
        prev = prev.next;
    }
}

巢狀類別：把實作細節藏得更深

是「只有 自己需要知道」的東西，所以我們把它宣告在類別裡面並標為 。 Java 有兩種寫法：

兩者在本節的用途下行為相同；課程講義用的是內部類別，實務上若不需要外層狀態，加 更省記憶體也更清楚。

練習