💻 DSA 互動式代碼研究室

public class ListNode {
    public Object data;
    public ListNode next;

    public ListNode(Object data) {
           this.data = data;
           this.next = null;
    }

    public ListNode(Object data, ListNode next) {
        this.data = data;
        this.next = next;
    }
}
            

public class LinkedList {
    private ListNode head;
    private ListNode tail;
    private int count;

    public LinkedList() {
        head = null; tail = null; count = 0;
    }

    public boolean isEmpty() { return (head==null); }
    public int getCount() { return count; }

    public void addToHead(Object item) {
        count++;
        if (isEmpty()) head = tail = new ListNode(item);
        else head = new ListNode(item, head);
    }

    public void addToTail(Object item) {
        count++;
        if (isEmpty()) head = tail = new ListNode(item);
        else { tail.next = new ListNode(item); tail = tail.next; }
    }

    public Object removeFromHead() throws EmptyListException {
        if (isEmpty()) throw new EmptyListException();
        count--; Object item = head.data;
        if (head == tail) head = tail = null;
        else head = head.next;
        return item;
    }

    public Object removeFromTail() throws EmptyListException {
        if (isEmpty()) throw new EmptyListException();
        count--; Object item = tail.data;
        if (head == tail) { head = tail = null; return item; }
        ListNode curr = head;
        while (curr.next != tail) curr = curr.next;
        tail = curr; tail.next = null;
        return item;
    }

    public String toString() {
        String s = "[ ";
        ListNode current = head;
        while (current != null) {
            s += current.data + " ";
            current = current.next;
        }
        return s + "]";
    }
}
            

public class ArrayStack implements Stack {
    public static final int CAPACITY=1000;
    private int capacity;
    private Object[] array;
    private int top = -1;

    public ArrayStack() {
        this(CAPACITY);
    }

    public ArrayStack(int cap) {
        capacity = cap;
        array = new Object[capacity];
    }

    public int size() {
        return top + 1;
    }

    public boolean isEmpty() {
        return (top < 0);
    }

    public void push(Object item) throws StackFullException {
        if (size() == capacity) throw new StackFullException();
        array[++top] = item;
    }

    public Object top() throws StackEmptyException {
        if (isEmpty()) throw new StackEmptyException();
        return array[top];
    }

    public Object pop() throws StackEmptyException {
        if (isEmpty()) throw new StackEmptyException();
        Object item = array[top];
        array[top--] = null;
        return item;
    }
}
            

public class LinkedStack implements Stack {
    private LinkedList list;

    public LinkedStack() {
        list = new LinkedList();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public int size() {
        return list.getCount();
    }

    public void push(Object item) throws StackFullException {
        list.addToHead(item);
    }

    public Object pop() throws StackEmptyException {
        try {
            Object item = list.removeFromHead();
            return item;
        } catch (EmptyListException ex) {
            throw new StackEmptyException();
        }
    }

    public Object top() throws StackEmptyException {
        try {
            Object item = list.removeFromHead();
            list.addToHead(item);
            return item;
        } catch (EmptyListException ex) {
            throw new StackEmptyException();
        }
    }
}
            

public class ArrayQueue implements Queue {
    public static final int CAPACITY=1000;
    private int capacity;
    private Object[] array;
    private int front=0;
    private int rear=0;

    public ArrayQueue() {
        this(CAPACITY);
    }

    public ArrayQueue(int cap) {
        capacity = cap;
        array = new Object[capacity];
    }

    public int size() {
        return (capacity - front + rear) % capacity;
    }

    public boolean isEmpty() {
        return (front == rear);
    }

    public void enqueue(Object item) throws QueueFullException {
        if (size() == capacity-1) 
            throw new QueueFullException();
        array[rear] = item;
        rear = (rear+1) % capacity;
    }

    public Object dequeue() throws QueueEmptyException {
        if (isEmpty()) throw new QueueEmptyException();
        Object item = array[front];
        array[front] = null;
        front = (front+1) % capacity;
        return item;
    }

    public Object front() throws QueueEmptyException {
        if (isEmpty()) throw new QueueEmptyException();
        return array[front];
    }

    public String toString() {
        String s = "[ ";
        int next = front;
        for (int i=0; i<size(); i++) {
            s += array[next] + " ";
            next = (next+1) % capacity;
        }
        return s + "]";
    }
}
            

public class LinkedQueue implements Queue {
    private LinkedList qll;

    public LinkedQueue() {
        qll = new LinkedList();
    }

    public int size() { return qll.getCount(); }

    public boolean isEmpty() { return qll.isEmpty(); }

    public void enqueue(Object item) throws QueueFullException {
        qll.addToTail(item);
    }

    public Object dequeue() throws QueueEmptyException {
        try {
            Object item = qll.removeFromHead();
            return item;
        } catch (EmptyListException e) {
            throw new QueueEmptyException();
        }
    }

    public Object front() throws QueueEmptyException {
        try {
            Object item = qll.removeFromHead();
            qll.addToHead(item);
            return item;
        } catch (EmptyListException e) {
            throw new QueueEmptyException();
        }
    }

    public String toString() {
        return qll.toString();
    }
}
            

ListNode.java

定義鏈結串列 (Linked List) 中的基本儲存單位「節點」。

💡 這是所有鏈結結構的物理基礎，請點擊左側代碼查看細節。

💡 點擊左側程式碼行，查看關鍵字解釋與邏輯分析

🏷️ public class

定義一個公開類別。這代表該檔案可以被其他 Package 存取。Java 規定一個檔案內只能有一個與檔案名稱相同的 public class。

🔌 implements

代表該類別「實作」了介面（Interface）。這體現了物件導向中的多型 (Polymorphism)。

🧱 數據成員 (Fields)

Object data: 儲存實際內容。
ListNode next: 儲存下一個節點的地址。這種寫法稱為自引用 (Self-referential)。

🎯 關鍵字：this

在建構子中，使用 this.data 明確指定：「把傳進來的參數值，存進這個物件本身的屬性裡」，避免名稱衝突。

🧹 next = null

當新建立一個孤立節點時，預設沒有下一個節點。null 也是單向鏈結串列尋找「尾巴」的終點標誌。

🔗 鏈結建構子

此建構子非常高效，可以直接將新節點的 next 指向舊頭部，一行代碼完成連結。

🏷️ public class LinkedList

單向鏈結串列的主體。與陣列不同，資料不需要連續存放，而是依靠 next 指標像火車車廂一樣串接。

📏 getCount()

直接回傳目前維護的 count 變數。時間複雜度為 O(1)。

📈 更新計數器

新增任何節點的第一件事，就是將總數 count 加 1。

🌟 空串列新增

與 addToHead 相同。空串列加入第一個元素時，首尾必定是同一個節點。

🛡️ 防呆機制

如果串列已經是空的，根本沒東西可刪，拋出異常防止 NullPointerException。

💾 備份資料與更新計數

扣除 count，並把即將被刪除節點的資料存起來，以免節點被拔掉後找不回來。

🌟 只剩一個節點

如果 head == tail，代表全村只剩這一個節點。刪除它之後串列就空了。

📤 回傳資料

將稍早備份好的資料丟回給呼叫這個方法的人。

🌟 只剩一個節點

如果只剩一個，清空 head 和 tail，並回傳資料即可。此情況下為 O(1)。

🔄 更新尾部指標

找到倒數第二個節點後，把它設定為新的 tail，並且把它的 next 斬斷 (設為 null)。

📤 回傳資料

將尾部原本的資料回傳。

📍 Head 與 Tail 指標

維護 tail 指標是為了讓尾部新增資料時，能瞬間找到位置。

⚡ 時間複雜度降為：O(1)

🔢 count (計數器)

額外宣告一個變數追蹤節點數量，這樣 getCount() 就不需要從頭數到尾了。

🏗️ 建構子

初始化時，串列是空的，所以 head 和 tail 都是 null。

❓ isEmpty() 檢查

判斷串列是否為空的最快方式，就是看 head 是不是 null。

➕ addToHead

將新資料插入最前面。這是實作 Stack `push` 的底層基礎。

⚡ 時間複雜度：O(1)

🌟 空串列新增

如果原本串列是空的，新加入的節點同時會是第一個與最後一個，所以 head 和 tail 都要指向它。

🔄 一般頭部新增

建立新節點，把它的 next 指向舊 head，然後把 head 標籤移給新節點。

➕ addToTail

因為我們有維護 tail 指標，這常被用來實作 Queue 的 enqueue。

⚡ 時間複雜度：O(1)

🔄 一般尾部新增

讓原本最後一節車廂的 next 指向新車廂，然後將 tail 標籤移動到真正的最後一節車廂上。

✂️ removeFromHead

拔掉串列的第一個節點並回傳。常被用作 Stack 的 pop 或 Queue 的 dequeue。

⚡ 時間複雜度：O(1)

🔄 一般頭部刪除

直接讓頭部指標往後退一格。原本的舊頭部會被 Java 垃圾回收器 (GC) 清掉。

✂️ removeFromTail

移除並回傳最後一個節點。這是單向鏈結串列最痛苦的操作！

🐢 痛苦的遍歷 (Traversal)

因為單向串列不知道自己的前一個是誰，為了更新 tail，必須指派一個指標從頭開始一格一格找，直到找到倒數第二個節點。

🐢 時間複雜度：O(n)

🖨️ toString() 方法

覆寫物件的預設字串表示法。當使用 System.out.println(list) 時，會自動呼叫這個方法。

🚶 走訪 (Traversal) 邏輯

這是鏈結串列中最核心的公式：

current = head：從頭開始。
current != null：只要車廂存在就繼續。
current = current.next：沿著指標走到下一節車廂。

🚶 時間複雜度：O(n)

📤 回傳結果

將收集到的資料拼接成字串並回傳。

🏷️ public class ArrayStack implements Stack

這行宣告了一個名為 ArrayStack 的類別，並且它必須遵循 Stack 介面規定的所有合約（push, pop, top 等）。

📢 public static final int CAPACITY

public static: 全域共享。
final: 代表這是常數，一旦設定就不能更改。
這裡定義了如果使用者沒指定大小，預設就是 1000 個格位。

容量變數 (capacity)

這是一個私有變數，用來記錄「當前」這個堆疊實例真正被分配到的空間大小。

📦 Object[] array

堆疊的真實儲存空間。我們使用 Object 陣列，這樣可以放入任何種類的 Java 物件（字串、數字、自定義類別等）。

🔝 top 索引指標

這是 Stack 的靈魂。它永遠標記著目前「最頂層」資料在哪個位置。初始化為 -1 代表連第 0 個索引都還沒用到，堆疊目前為空。

🎯 預設建構子與 this()

當你直接執行 new ArrayStack() 時，它會調用 this(CAPACITY)，這是一種代碼重用技巧，自動幫你帶入 1000 這個預設值。

🏗️ 帶參數的建構子

允許使用者自定義堆疊大小。這是在執行期間分配記憶體空間的時刻。

💾 記憶體分配細節

new Object[capacity] 會在 Java Heap 區域劃分出一塊連續的空間來存放物件的參照。

📏 size() 計算

因為索引從 0 開始，所以當 top 是 2 時，裡面有 0, 1, 2 三個東西。回傳 top + 1 正確反映數量。

⚡ O(1)

❓ isEmpty() 檢查

檢查邏輯非常簡單：只要 top 還是小於 0，就代表沒東西。

⚡ O(1)

🚀 push 方法簽署

將資料壓入堆疊。注意它宣告了 throws StackFullException，因為陣列空間是有限的，滿了就必須報錯。

🛡️ 滿堆疊檢查

在放入資料前，必須先確認是否還有位置。如果 size() == capacity，程式會立即噴出異常，防止陣列索引越界。

⚡ 關鍵：array[++top] = item

++top: 先將指標往上移一格。
array[index] = item: 將資料填入新位置。

這是最簡潔且正確的 Stack 寫法。

👀 top() / Peek 方法

回傳堆疊最上面的東西，但不移除它。就像偷看最上面的公文一樣。

🛡️ 空堆疊檢查 (top)

如果你試圖看一個空箱子，Java 會拋出 StackEmptyException。

📤 回傳資料 (不變動指標)

直接透過 array[top] 取值。此時 top 變數本身的值完全沒變。

✂️ pop 方法簽署

移除並回傳最上面的元素。這是 Stack 中最常用的破壞性操作。

💾 暫存回傳值

我們必須先把最上面的東西拿出來存在 item 變數裡，因為下一行我們就要把那個位置清空了。

🗑️ 清除 Loitering (專業必考點)

array[top--] = null 包含兩個重要動作：

null: 將格位清空，讓垃圾回收器 (GC) 回收這塊記憶體。
top--: 動作完後，將指標往下移一格。

📤 完成回傳

將存好的 item 回傳給呼叫者。此時堆疊的高度已經減少了 1。

⚡ O(1)

🏷️ public class LinkedStack implements Stack

宣告一個基於鏈結串列實作的堆疊。因為它實作了 Stack 介面，所以外面的使用者操作它時，感覺跟 ArrayStack 一模一樣，這展現了物件導向中「隱藏實作細節」的優勢。

📦 Adapter 模式 (包裝類 / 轉接器)

注意看！這裡沒有宣告 Node，也沒有宣告陣列，而是宣告了一個 LinkedList。這代表 LinkedStack 本身不負責管理記憶體，它只是把收到的指令「轉交」給底層的串列去處理。

🏗️ 預設建構子

在此將內部的 list 實例化為一個全新的空串列。注意：因為鏈結串列的特性，這裡不需要宣告容量 (Capacity)，它可以無限延伸直到電腦記憶體耗盡。

❓ isEmpty() 方法映射

直接呼叫 list.isEmpty()，這稱為方法委派 (Method Delegation)。

⚡ O(1)

📏 size() 方法映射

直接呼叫 list.getCount()，因為我們在 LinkedList 裡有好好維護 count 變數，所以這裡也是極快的 O(1)。

🚀 push() -> addToHead()

Stack 的特性是「後進先出 (LIFO)」。為了達到 O(1) 的超高效率，我們把新資料壓在串列的最前端 (Head)，因為操作 Head 是最快的！

✂️ pop() 方法

將最上層的資料彈出。對應的底層操作就是把串列的頭部 (Head) 砍掉並取出資料。

🔄 嘗試呼叫 removeFromHead()

我們在 try 區塊中大膽地呼叫串列的 removeFromHead() 方法。

⚡ 時間複雜度：O(1)

🛡️ 異常翻譯 (Exception Translation)

這是一個非常專業的考點！因為底層是 LinkedList，如果串列是空的，它會拋出 EmptyListException。

但是對外面呼叫 pop() 的人來說，他只知道這是一個 Stack，他不知道底層是 List，給他 List 異常他會一頭霧水！所以我們必須把它「攔截」下來，改拋出符合 Stack 語境的 StackEmptyException。

👀 top() 偷看方法

只看最上層的資料，不改變堆疊內容。

🛠️ 偷吃步的實作邏輯

因為原本的 LinkedList 類別沒有提供 getHead() 方法給我們看第一筆資料，我們只好用一個「偷吃步」：

先用 removeFromHead() 把資料拔出來。
立刻用 addToHead() 把它塞回去。
再把資料回傳。

雖然多做了一點事，但整體仍然是 O(1)。更好的做法其實是去修改 LinkedList，幫它加一個唯讀的方法！

🛡️ 異常翻譯 (top)

跟 pop() 的邏輯一模一樣，把底層的 EmptyListException 包裝成 StackEmptyException。

🏷️ public class ArrayQueue implements Queue

宣告一個基於陣列實作的隊列。它必須遵守 Queue 介面，也就是先進先出 (FIFO) 的規則。

📢 容量宣告

定義隊列的陣列大小。這裡使用了建構子串接 (this(CAPACITY))，若未指定則預設分配 1000 個格子。

📦 Object[] array

循環隊列的真實儲存空間。陣列大小在建立時就固定了，由 capacity 決定。

🚪 front 與 rear 指標

front: 永遠指向排隊的第一個人（準備被 dequeue 的位置）。
rear: 永遠指向下一個空著的位置（準備被 enqueue 的位置）。

兩者一開始都設為 0，代表空隊列。

🏗️ 建構子與 this()

支援無參數與帶參數的建構子。初始化陣列以備後續的入隊操作。

📏 神奇的 size() 公式

(capacity - front + rear) % capacity。因為是循環陣列，rear 有可能會繞了一圈跑到 front 的前面，直接相減 rear - front 會變成負數！

加上 capacity 再取模 %，是數學上保證能完美算出兩者距離的公式。

⚡ 時間複雜度：O(1)

❓ isEmpty() 邏輯

只要 front == rear，就代表現在隊列裡沒有人在排隊。這也是為什麼我們必須「浪費一個格子」的原因，如果允許全滿，那全滿時也會是 front == rear，電腦就無法分辨是滿還是空了！

📥 enqueue (入隊)

將資料加入隊列尾端。因為陣列大小固定，如果滿了必須拋出 QueueFullException。

🛡️ 滿隊列檢查 (浪費一格的藝術)

這裡的判斷是 size() == capacity - 1。這意味著一個 capacity 為 10 的陣列，最多只能裝 9 個元素！保留一個空位是為了讓 rear 永遠不會追上 front。

🔄 % capacity 循環入隊

先把資料放進 rear 的空位，然後 rear 往後移一格。如果 rear 走到了陣列盡頭（例如 capacity=10，走到了 index 9），(9+1) % 10 = 0，它就會神奇地繞回陣列最前面的第 0 格！

📤 dequeue (出隊)

將排在隊列最前面的人移除並回傳。這也是破壞性操作。

🛡️ 空隊列防呆檢查 (dequeue)

出隊前必須先檢查是否為空，否則會發生從空陣列取值的錯誤，拋出 QueueEmptyException。

🗑️ 清除 Loitering

取出 array[front] 的資料後，必須把該格設為 null，讓 Java 的垃圾回收器 (GC) 回收這塊已經出隊的資料。

🔄 循環出隊

將 front 指標往後移一格。同樣透過 (front+1) % capacity 確保指標走到盡頭時會自動繞回開頭。

📤 完成回傳

回傳剛剛取出的最前端資料，完成出隊動作。

👀 front() 偷看方法

只回傳目前排在第一位的資料是誰，但不把它移出隊列。指標都不會改變。

🛡️ 空隊列防呆檢查 (front)

如果隊列是空的，沒有資料可以偷看，一樣拋出 QueueEmptyException。

📤 回傳前端資料

直接透過 array[front] 取值回傳，不更動指標。

🖨️ toString() 方法

覆寫字串輸出。為了印出正確順序，必須從 front 開始，沿著循環軌跡走到 rear 之前。

🚶 循環隊列的走訪 (toString)

這裡不能用傳統的 for(int i=0; i < array.length; i++)！因為資料在陣列中可能是斷開成兩截的（一部分在尾巴，一部分在開頭）。

正確解法：宣告一個 next 變數從 front 開始，總共跑 size() 次，每次印出後，讓 next = (next+1) % capacity 模擬指標循環前進的軌跡。

🐢 時間複雜度：O(n)

🛡️ 空堆疊防呆檢查 (pop)

如果堆疊已經是空的 (top < 0)，此時執行 pop 會拋出 StackEmptyException，防止發生 ArrayIndexOutOfBoundsException。

🔄 % capacity (取模運算)

循環隊列的靈魂。當指標走到陣列末端，(index + 1) % capacity 會讓指標自動「繞回」開頭。

🏷️ public class LinkedQueue implements Queue

宣告一個基於鏈結串列實作的隊列。實作了 Queue 介面，對外保證提供先進先出 (FIFO) 的操作。

📦 Adapter 模式 (包裝類)

就像 LinkedStack 一樣，內部隱藏了一個 LinkedList 變數 (qll)。它不需要像 ArrayQueue 那樣維護複雜的 front 和 rear 指標運算，這些髒活累活都交給內部的串列處理了。

🏗️ 預設建構子

實例化內部的 LinkedList。不需要傳入 Capacity（容量），因為鏈結串列可以無限擴充。

📏 size() 方法映射

直接呼叫 qll.getCount()。將 Queue 索取大小的請求，委派給內部的 List。

⚡ 時間複雜度：O(1)

❓ isEmpty() 方法映射

直接呼叫 qll.isEmpty()。

⚡ 時間複雜度：O(1)

📥 enqueue (入隊)

雖然方法宣告了可能拋出 QueueFullException（為了符合 Queue 介面的合約），但在 LinkedQueue 的實作中，因為記憶體可以一直增加，實際上幾乎不會拋出這個異常。

🚀 addToTail (尾部新增)

這行是期末考重點！ 隊列是排隊，新來的人必須排在最後面，所以對應的是串列的 addToTail()。

💡 因為我們的 LinkedList 裡面有維護 tail 指標，所以即使是尾部新增，速度也非常快！

⚡ 時間複雜度：O(1)

📤 dequeue (出隊)

隊列是先進先出 (FIFO)，最先排隊的人在最前面，所以出隊操作對應的是串列的「頭部刪除」。

✂️ removeFromHead (頭部刪除)

呼叫串列的 removeFromHead() 把排在第一位的人移出來並回傳。

⚡ 時間複雜度：O(1)

🛡️ 異常翻譯 (Exception Translation)

攔截 LinkedList 拋出的 EmptyListException，將其包裝成符合 Queue 語境的 QueueEmptyException，完美隱藏底層是用 List 實作的秘密。

👀 front() 偷看方法

只查看排在第一位的是誰，不把它移出隊列。

🛠️ 偷吃步的實作邏輯

跟 LinkedStack 一樣的套路！先用 removeFromHead() 把資料拔出來看一眼，然後馬上用 addToHead() 把它原封不動塞回車頭。

⚡ 時間複雜度：O(1)

🛡️ 異常翻譯 (front)

攔截並轉換為 QueueEmptyException。

🖨️ toString() 方法映射

直接呼叫 qll.toString()。不需要自己寫 while 迴圈走訪，因為 LinkedList 已經幫我們實作好了！這就是封裝與代碼重用最棒的體現。

🔄 異常包裝

攔截底層 LinkedList 的 EmptyListException，並重新拋出符合當前資料結構語境的 StackEmptyException。