环形缓冲区把一段固定长度的存储空间视为首尾相接。读写位置到达末端后回到开头,从而反复利用已经释放的位置。
任务说明
循环缓冲区,也称环形缓冲区,把一块固定大小的存储空间当作首尾相连的数据结构使用。
缓冲区初始为空,长度预先确定。例如,下面是长度为 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]