원형 버퍼

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

동작[편집]

Circular buffer - empty.svg

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

Circular buffer - XX1XXXX.svg

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

Circular buffer - XX123XX.svg

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

Circular buffer - XXXX3XX.svg

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

Circular buffer - 6789345.svg

구현[편집]

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

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

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