環狀緩衝區

說明

環狀緩衝區、循環緩衝區或環形緩衝區是一種資料結構，它把單一且固定大小的緩衝區當成頭尾相連來使用。

環狀緩衝區一開始是空的，並帶有某個預先定義好的長度。舉例來說，這是一個有 7 個元素的緩衝區：

[ ][ ][ ][ ][ ][ ][ ]

假設把 1 寫進緩衝區的中間（在環狀緩衝區裡，實際的起始位置並不重要）：

[ ][ ][ ][1][ ][ ][ ]

接著假設又加入兩個元素，也就是 2 和 3，它們會被附加在 1 的後面：

[ ][ ][ ][1][2][3][ ]

如果接著從緩衝區移除兩個元素，被移除的會是緩衝區裡最舊的值。在這個例子中，被移除的兩個元素是 1 和 2，緩衝區裡只剩下 3：

[ ][ ][ ][ ][ ][3][ ]

如果緩衝區裡有 7 個元素，就代表它完全滿了：

[5][6][7][8][9][3][4]

緩衝區滿了之後會引發錯誤，提醒用戶端在有空位釋出之前，後續的寫入都會被封鎖。

緩衝區滿了的時候，用戶端可以選擇用強制寫入來覆寫最舊的資料。在這個例子中，又加入兩個元素 A 和 B，它們會覆寫掉 3 和 4：

[5][6][7][8][9][A][B]

3 和 4 已被 A 和 B 取代，現在緩衝區裡最舊的資料變成了 5。最後，如果移除兩個元素，回傳的會是 5 和 6，緩衝區就變成：

[ ][ ][7][8][9][A][B]

因為現在有空出來的空間，如果用戶端再次使用覆寫來存入 C 和 D，用的會是先前存放 5 和 6 的空間，而不是 7 和 8 的位置。7 仍然是最舊的元素，而緩衝區又再次滿了。

[C][D][7][8][9][A][B]

---

出處

Wikipedia