AY 22-23 Final Exam - Question A4 解答

題目設定

一個佇列 (Queue) 使用環狀陣列 (Circular Array) 實作。目前名為 Q 的環狀陣列佇列狀態如下：

Index	0	1	2	3	4	5	6
Content	null	null	null	Hedgehog	Rabbit	Dog	Cat

(a) 如果這個佇列 Q 是空的，它最多可以儲存多少個資料（maximum number of data）？（1 mark）
(b) 如果 front 的索引值是 3（指向 Hedgehog），請問 rear 的索引值會是多少？（1 mark）
(c) 程式碼中，我們該如何利用 front 和 rear 來檢查這個佇列是否為空（is empty）？（1 mark）
(d) 假設佇列 Q 現在被清空並重置（也就是 front = rear = 0）。請追蹤並寫出執行完以下程式碼後，陣列中 Index 0 到 6 的最終內容（final contents）：（7 marks）
```
for (int k = 1; k <= 6; k++)
    Q.enqueue(k);

for (int k = 1; k <= 4; k++) {
    Q.enqueue(Q.dequeue());
    Q.dequeue();
}
```
(e) 佇列也可以使用鏈結串列（Linked List）來實作。請寫出使用 Linked List 來實作 Queue，相較於使用陣列（Array），有哪 ONE advantage（一個優點）以及 ONE disadvantage（一個缺點）？（2 marks）

本陣列總長度（Capacity）為 7。為了避免 front == rear 時無法分辨「全滿」與「全空」，環狀陣列設計通常會犧牲一個空位，因此最多可放 N - 1 個資料。
在教材實作中，front 指向隊首（第一個元素），而 rear 指向下一個可放入新資料的空位（the index to the next available array element）。
檢查是否為空的標準寫法是：當 front 與 rear 相等時，佇列為空。
在追蹤 (d) 題時，注意每次 dequeue() 被呼叫後，該位置會被設回 null（例如：array[front] = null;）。建議用紙筆畫出 7 個格子並標示 front/rear 的變化來模擬每一步。
Linked List 的優缺點：Linked List 可動態增長，不會受固定容量限制；但每個節點需額外儲存指標（next），增加記憶體開銷。

答案： 6

解析：陣列長度為 7，但環狀佇列設計犧牲一個空位以區分「全滿」與「全空」，因此最多可放 7 - 1 = 6 個資料。

答案： 0

解析：front 指向 Index 3（Hedgehog），目前元素佔據 Index 3, 4, 5, 6（共 4 個）。下一個可放入的空位是 Index 6 往後加 1，繞回到 0（使用模數運算：(6 + 1) % 7 = 0）。

答案（標準寫法）： front == rear

解析：當兩個指標相遇時表示沒有元素；雖然 front = rear = 0 是一種空的初始狀態，但更通用的判斷是比較兩者是否相等。

💡 初始狀態：重置後 front = 0, rear = 0，陣列為 [null, null, null, null, null, null, null]

第一階段（enqueue 1 到 6）結果：

[1, 2, 3, 4, 5, 6, null]
(front = 0, rear = 6)

第二階段（重複 4 次：enqueue(dequeue()), dequeue()）逐步模擬：

k = 1
- dequeue() 拿出 1 → 原位置設為 null，front 移至 1
- enqueue(1) 放到 rear（Index 6）→ 陣列尾端補 1，rear 繞回 0
- dequeue() 拿出 2 → 原位置設為 null，front 移至 2
```
[null, null, 3, 4, 5, 6, 1]
```
k = 2
- dequeue() 拿出 3 → 原位置設為 null，front 移至 3
- enqueue(3) 放到 rear（Index 0）→ 數字 3 放入 Index 0, rear 移至 1
- dequeue() 拿出 4 → 原位置設為 null，front 移至 4
```
[3, null, null, null, 5, 6, 1]
```
k = 3
- dequeue() 拿出 5 → 原位置設為 null，front 移至 5
- enqueue(5) 放到 rear（Index 1）→ 數字 5 放入 Index 1, rear 移至 2
- dequeue() 拿出 6 → 原位置設為 null，front 移至 6
```
[3, 5, null, null, null, null, 1]
```
k = 4
- dequeue() 拿出 1 → 原位置設為 null，front 繞回 0
- enqueue(1) 放到 rear（Index 2）→ 數字 1 放入 Index 2, rear 移至 3
- dequeue() 拿出 3 → 原位置設為 null，front 移至 1
```
[null, 5, 1, null, null, null, null]
```

🎉 最終答案（Final Contents）：

Index	0	1	2	3	4	5	6
Content	null	5	1	null	null	null	null

Advantage（優點）： 可以動態增長與縮減，不會受固定容量限制（No fixed capacity; grows/shrinks as needed）。

Disadvantage（缺點）： 每個節點需額外儲存指標（next），因此比陣列需要更多額外的記憶體開銷（Extra memory per node for pointers）。

💡 教授的總結與學習建議：

環狀陣列的設計重點在於用模數運算處理索引繞回（wrap-around），並犧牲一個空位以區分「全滿」與「全空」。
追蹤題（像 (d) 題）最容易出錯的地方是忘記把被 dequeue 的位置設回 null，或是沒有正確更新 front/rear 的繞回邏輯。
實戰技巧：考試時務必用紙筆畫格子、標示 front/rear，一步一步模擬 enqueue/dequeue，並在每一步寫下 front/rear 的新值，絕不能單靠大腦空想。