원형 버퍼

원형 버퍼(영어: circular buffer)는 고정된 크기의 버퍼를 양 끝이 연결된 것처럼 사용할 수 있게 해주는 자료 구조이다. 원형 버퍼를 이용하면 거의 성능 저하 없이 단순 배열을 덱처럼 사용할 수 있다.

동작

빈 원형 버퍼에 다음과 같이 1이 입력되었다고 하자.(정확한 시작 위치는 원형 버퍼에서는 중요치 않다)

그리고 2와 3이 추가로 입력되면 다음과 같이 3개의 원소를 갖게 된다.

이 중 두 개의 원소가 출력되면 1과 2가 사라지고 3이 남게 된다.

이 버퍼의 크기는 7이므로 7개의 원소가 입력되면 꽉 차게 된다.

구현

원형 버퍼는 대개 4개의 요소로 이루어진다.

• 고정된 크기의 배열
• 배열의 크기
• 제일 처음 입력된 데이터의 위치
• 마지막으로 입력된 데이터의 위치

마지막으로 입력된 데이터의 위치 대신, 입력된 데이터의 개수를 저장하는 경우도 있다.