环形缓冲区

说明

环形缓冲区（circular buffer），也叫循环缓冲区或环形缓冲区，是一种数据结构。它使用单个固定大小的缓冲区，就好像这个缓冲区的首尾是相连的。

环形缓冲区一开始是空的，长度是预先设定好的。 例如，下面是一个包含 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