解題說明
Design Circular Queue
題目描述：設計一個環形佇列（Circular Queue）的實作。環形佇列是一種線性資料結構，尾端連接到前端形成環形，能有效利用空間。需要實作 enQueue、deQueue、Front、Rear、isEmpty、isFull 等操作。
解題思路：使用固定大小的陣列和兩個指標 front 和 rear 來實作。關鍵在於用取餘運算 % 來實現環形效果：
front指向佇列前端元素。rear指向佇列最後一個元素的下一個位置。- 用一個
count變數追蹤當前元素數量，以區分佇列為空和佇列已滿的情況。 enQueue：在rear位置放入元素，rear = (rear + 1) % k。deQueue：移動front = (front + 1) % k。
C++ 解法
複雜度分析
時間複雜度：O(1) — 所有操作（enQueue、deQueue、Front、Rear、isEmpty、isFull）都是常數時間。
空間複雜度：O(k) — k 為佇列容量，需要固定大小的陣列。
虛擬碼
1. Initialize array of size k, front = 0, rear = 0, count = 0 2. enQueue(value): a. If full, return false b. data[rear] = value, rear = (rear + 1) % k, count++, return true 3. deQueue(): a. If empty, return false b. front = (front + 1) % k, count--, return true 4. Front(): return isEmpty ? -1 : data[front] 5. Rear(): return isEmpty ? -1 : data[(rear - 1 + k) % k] 6. isEmpty(): return count == 0 7. isFull(): return count == k
其他解法
鏈結串列實作：用單向鏈結串列加上 head、tail 指標和 count。不需要預先分配固定大小，但每個節點需要額外的指標空間。時間複雜度同為 O(1)，空間複雜度 O(k)。
不用 count 的陣列實作：多分配一個空間（大小 k+1），用 front == rear 判空，用 (rear + 1) % (k+1) == front 判滿。省去 count 變數，但浪費一個陣列位置。
延伸思考
- 如何將此設計擴展為雙端環形佇列（Design Circular Deque, LeetCode 641）？
- 在多執行緒環境下，如何保證環形佇列的執行緒安全？
- 如果需要支援動態擴容，該如何修改設計？