解題說明
Design Circular Deque
題目描述：設計一個固定容量的環形雙端佇列（Circular Deque），支援從前端和後端插入、刪除元素，以及取得前端、後端元素和判斷空、滿。
解題思路：使用固定大小的陣列和兩個指標 front、rear 實作環形結構。額外維護一個 size 變數追蹤當前元素數量，簡化空滿判斷。front 指向隊首元素，rear 指向隊尾元素。插入前端時 front 向前移動（取模），插入後端時 rear 向後移動（取模）。所有操作均為 O(1)。
C++ 解法
複雜度分析
時間複雜度：所有操作均為 O(1)。
空間複雜度：O(k) — 其中 k 為指定的容量大小。
虛擬碼
1. Constructor(k): allocate array of size k, set front = 0, rear = k-1, size = 0 2. insertFront(value): if full return false; front = (front - 1 + k) % k; data[front] = value; size++ 3. insertLast(value): if full return false; rear = (rear + 1) % k; data[rear] = value; size++ 4. deleteFront(): if empty return false; front = (front + 1) % k; size-- 5. deleteLast(): if empty return false; rear = (rear - 1 + k) % k; size-- 6. getFront(): if empty return -1; return data[front] 7. getRear(): if empty return -1; return data[rear] 8. isEmpty(): return size == 0 9. isFull(): return size == k
其他解法
雙向鏈結串列實作：用雙向鏈結串列加上計數器。插入刪除都是 O(1) 且不需要預先分配固定大小的陣列，可以動態調整容量。但記憶體碎片和指標開銷較大。
不用 size 變數的環形陣列：分配 k+1 格空間，用 front == rear 判空，(rear + 1) % (k+1) == front 判滿。避免額外變數但浪費一格空間。
延伸思考
- 如何擴展為支援動態擴容（當滿時自動倍增容量）？
- 環形佇列在作業系統中有哪些實際應用？（提示：IO 緩衝區、生產者-消費者模型）
- 若要支援多線程安全，需要在哪些操作加鎖？能否用無鎖設計？