环形缓冲区

说明

环形缓冲区（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]

---

来源

Wikipedia