🏗️ 第 1 週：資料結構基礎（Data Structures） 10/150
10.第一周小結和測驗:數組模擬環形隊列的實作 - 練習加深理解，確保學會了！
第一周複習:
核心主題：從線性思維到空間優化
這週的旅程從巨觀的概念開始，進入到具體的陣列操作，最後解決了實際工程中的記憶體浪費問題。1. 內功心法 (單元 1-2)
· 靈魂與骨架：確立了「程式 = 資料結構 + 演算法」的觀念。資料結構是載體（骨架），演算法是解決問題的步驟（靈魂）。
· 維度認知：區分了線性結構（一對一，如陣列、隊列）與非線性結構（一對多/多對多，如樹、圖）。
2. 空間優化：稀疏陣列 (單元 3-5)
· 痛點：當數據中充滿了無意義的 0（如五子棋盤、地圖），傳統二維陣列浪費大量空間。
· 解法：透過 稀疏陣列 (Sparse Array) 進行壓縮，只記錄「行、列、值」。
· 價值：學會了「以時間換空間」或「以邏輯換空間」的優化思維。
3. 線性緩衝：隊列與環形 (單元 6-9)
· 基礎隊列：模擬生活中的排隊（FIFO），但在陣列實作中遇到了 「假溢出」 問題——明明前面有空位，卻因為指標回不去而無法使用。
· 進階解法 (環形隊列)：
o 引入 取餘數運算 (%)，將直線陣列「折彎」成圓環。
o 犧牲一個空間 用於區分「空」與「滿」，徹底解決了空間浪費問題。
o 這是作業系統與通訊緩衝區（Buffer）的底層原理。
接下來，我們正式進入 第 10 單元。既然第 9 單元已經通透了概念，第 10 單元就是要把這個邏輯轉化為 可運行的程式碼，並透過測驗確保您完全掌握。
一、 Python 實作範例
請對照上一單元的公式，閱讀以下程式碼。這段代碼是 LeetCode 622 設計環形隊列的標準解法之一。請試著在腦中模擬 enqueue 和 dequeue 時指針的移動。
class MyCircularQueue:
def __init__(self, k: int):
# We use k+1 size array to distinguish full and empty
self.capacity = k + 1
self.queue = [0] * self.capacity
# front: points to first element
# rear : points to next insertion position
self.front = 0
self.rear = 0
def enQueue(self, value: int) -> bool:
# Check if queue is full
if self.isFull():
return False
# Insert element
self.queue[self.rear] = value
# Move rear forward circularly
self.rear = (self.rear + 1) % self.capacity
return True
def deQueue(self) -> bool:
# Check if queue is empty
if self.isEmpty():
return False
# Move front forward circularly
self.front = (self.front + 1) % self.capacity
return True
def Front(self) -> int:
# Return front element
if self.isEmpty():
return -1
return self.queue[self.front]
def Rear(self) -> int:
# Return last element
if self.isEmpty():
return -1
return self.queue[(self.rear - 1 + self.capacity) % self.capacity]
def isEmpty(self) -> bool:
# front meets rear -> empty
return self.front == self.rear
def isFull(self) -> bool:
# next position of rear is front -> full
return (self.rear + 1) % self.capacity == self.front
二、 AI電信視角 (Telecom Context)
既然這是在您的 AI時代系列 課程中，我們必須連結到通訊實務，這也是您為什麼要學這個結構的原因：
應用場景：環形緩衝區 (Ring Buffer)
在 4G/5G 的 RLC 層 (Radio Link Control) 或路由器的 Port Buffer 中，資料封包（Packets）源源不絕地進來。
· 為何不用一般隊列？ 一般隊列在元素出隊後，需要頻繁的數據搬移（Data Shifting）來填補空位，這會造成巨大的 CPU 負擔和延遲（Latency）。
· 環形優勢： 環形隊列允許我們在固定的記憶體區塊（例如一個 1MB 的 buffer）中不斷地覆寫舊資料、寫入新資料，這對於處理 高吞吐量 (Throughput) 的串流數據至關重要。
· 實務細節： 若 Buffer 滿了（isFull 為真），新的封包通常會被直接丟棄（Packet Drop），這就是網路壅塞時發生「掉包」的底層原因之一。
Q1. 索引計算
假設一個環形隊列的陣列大小（Capacity，包含預留位）為 5（即索引 0~4）。
目前 front = 3, rear = 0。請問：
- 隊列現在是空的、滿的、還是有資料？
- 如果執行一次 deQueue()，front 會變成多少？
- 如果執行一次 enQueue(X)，rear 會變成多少？
✅ 答案解析：
- front ≠ rear → 不是空 (rear + 1) % 5 = 1 ≠ front(3) → 不是滿 👉 目前有資料
front = (3 + 1) % 5 = 4
👉 front = 4
rear = (0 + 1) % 5 = 1
👉 rear = 1
Q2. 判滿邏輯
為什麼在判斷「滿」的時候，公式是
(rear + 1) % capacity == front，
而不是直接看 rear == front？
如果不預留那一個空位，會發生什麼混淆？
✅ 答案解析：
- front == rear 已被定義為「空」
- 若滿也用 rear == front，將無法區分空或滿
- 因此預留一格空位，用下一格是否追上 front 來判斷
👉 避免空與滿混淆
Q3. 實務除錯 (Debug)
如果您在撰寫 5G 基地台的封包緩衝程式，
您宣告了 size = 100 的陣列想存 100 個封包。
但發現每次存到第 100 個時系統就報錯說「滿了」並丟棄封包。
根據上面的實作邏輯，這是什麼原因？
✅ 答案解析：
- 環形隊列必須預留 1 個空位
- size = 100 時，實際只能存 99 筆
- 若要存 100 筆，需宣告：
capacity = 101
👉 錯誤來自未考慮預留空位
✅ 一句話總結
想存 N 筆資料，陣列大小要設 N + 1。
