**circular buffer(원형 버퍼)**는 양 끝이 고리로 이어진 것처럼 다뤄지는 고정 크기 array입니다. 두 인덱스인 **head(읽기)**와 **tail(쓰기)**가 모듈로 연산을 사용해 진행하며 감싸 돌아가, 생성 후 할당 없이 O(1) FIFO 큐를 제공합니다.
감싸기(wrapping)가 동작하는 방식
text
용량 5, A,B,C,D를 쓰고 A,B를 읽은 후:
index: 0 1 2 3 4
[ . ][ . ][ C ][ D ][ . ]
head^ tail^ (tail은 다음 쓰기에서 0으로 감싸 돌아감)
코드
python
:
():
.buf = []*n
.head = .tail = .size =
.cap = n
():
.size == .cap: Exception()
.buf[.tail] = x
.tail = (.tail + ) % .cap
.size +=
():
x = .buf[.head]
.head = (.head + ) % .cap
.size -=
x
