環狀緩衝區

說明

環狀緩衝區、循環緩衝區或環形緩衝區是一種資料結構，它使用單一固定大小的緩衝區，就好像頭尾相連一樣。

環狀緩衝區一開始是空的，並有某個預先定義好的長度。 例如，這是一個有 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]

這個練習會介紹幾個你可能還沒遇過的概念：

自訂命名空間

在 8th 裡，所有的詞都屬於某個命名空間，例如a:new指的是a命名空間中的new詞。 你也可以定義自訂命名空間，我們在circular-buffer.8th檔案的開頭就是這麼做的：

ns: cb

這表示該檔案中的所有詞都可以透過cb:<word>來存取，這是把相關功能分組的好方法。

想了解更多資訊，請參閱命名空間文件。

例外

當read和write這兩個詞被呼叫在狀態無效的環狀緩衝區上時，都應該拋出例外。 想了解更多資訊，請參閱例外與錯誤處理文件。

物件

雖然你可以自由選擇實作環狀緩衝區的方式，但也可以考慮使用 8th 的物件支援。

---

出處

Wikipedia