MediumRating 1610
1670. Design Front Middle Back Queue
arraylinked-listdesignqueuedoubly-linked-listdata-stream
解題說明
Design Front Middle Back Queue
題目描述：設計一個佇列，支援在前端、中間和後端進行插入與刪除操作。中間位置定義為：若長度為偶數取前半末尾位置，奇數則取正中間。
解題思路：使用兩個雙端佇列（deque）front 和 back 維護資料，保持 front.size() == back.size() 或 front.size() == back.size() - 1 的平衡不變式。pushMiddle 時插入到 back 前端或 front 末端，popMiddle 時從 front 末端或 back 前端彈出。每次操作後呼叫 balance() 函式重新平衡兩個 deque，確保所有操作均為 O(1)。
C++ 解法
複雜度分析
時間複雜度：O(1)（每個操作）— 所有插入、刪除和平衡操作都是 deque 的前端或末端操作。
空間複雜度：O(n) — 兩個 deque 共儲存 n 個元素。
虛擬碼
1. Maintain two deques: front and back 2. Invariant: front.size() == back.size() or front.size() == back.size() - 1 3. balance(): if front too large, move front.back to back.front; if back too large, move back.front to front.back 4. pushFront: push to front.front, then balance 5. pushMiddle: if front.size < back.size, push to front.back; else push to back.front 6. pushBack: push to back.back, then balance 7. popFront: if empty return -1; pop front.front (or back.front if front empty), balance 8. popMiddle: if empty return -1; if sizes equal pop front.back, else pop back.front 9. popBack: if empty return -1; pop back.back, balance
其他解法
索引雙向鏈結串列：使用雙向鏈結串列並維護一個 middle 指標。每次操作後根據長度奇偶性調整 middle 指標前移或後移一步。所有操作 O(1)，但實作更繁瑣。
陣列 + 位移：用單一動態陣列管理，中間插入/刪除需要移動元素，時間 O(n)。簡單但不適合大量操作。
延伸思考
- 若「中間」的定義改為偶數長度時取右側，不變式要如何修改？
- 如何擴展支援 peekFront、peekMiddle、peekBack？
- 在多線程環境下，如何對兩個 deque 的平衡操作加鎖？