环形缓冲区

实践练习C++17

环形缓冲区把一段固定长度的存储空间视为首尾相接。读写位置到达末端后回到开头,从而反复利用已经释放的位置。

任务说明

循环缓冲区,也称环形缓冲区,把一块固定大小的存储空间当作首尾相连的数据结构使用。

缓冲区初始为空,长度预先确定。例如,下面是长度为 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]