环形缓冲区

说明

循环缓冲区、环形缓冲区或环状缓冲区是一种数据结构，它把一块固定大小的缓冲区当作首尾相连来使用。

循环缓冲区一开始是空的，长度则预先设定。例如，下面这个缓冲区有 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