원형 버퍼

지침

원형 버퍼, 순환 버퍼, 링 버퍼는 하나의 고정 크기 버퍼를 마치 끝과 끝이 연결된 것처럼 사용하는 자료 구조예요.

원형 버퍼는 처음에는 비어 있고, 미리 정해진 길이를 가져요. 예를 들어 다음은 요소 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를 저장하면, 7과 8이 있는 자리가 아니라 이전에 5와 6이 저장되어 있던 자리가 사용돼요. 7은 여전히 가장 오래된 요소이고, 버퍼는 다시 가득 찼어요.

[C][D][7][8][9][A][B]

---

출처

Wikipedia