원형 버퍼 (Circular Buffer / Ring Buffer)

고정 크기 배열 하나로 큐를 만든다. 끝에 도달한 포인터가 0번으로 되돌아오면서(wrap-around) 배열을 원형처럼 재사용한다. 데이터를 옮기지 않고 넣고 빼기가 모두 O(1).

1. 왜 원형인가?

보통 배열 큐는 앞에서 빼면 빈 칸이 생기고, 그 칸을 메우려면 뒤 원소를 전부 한 칸씩 당겨야 한다(O(n)). 아니면 큐가 배열 오른쪽으로 계속 밀려나 결국 공간이 모자란다.

원형 버퍼는 칸을 당기지 않는다. 대신 쓰는 위치(head) 와 읽는 위치(tail) 두 개의 인덱스만 옮기고, 배열 끝을 넘으면 % 용량 으로 0번으로 되돌린다. 물리적으로는 일직선 배열이지만, 인덱스 계산 덕분에 논리적으로는 고리가 된다.

# 다음 위치는 항상 이렇게 구한다
head = (head + 1) % capacity
tail = (tail + 1) % capacity

2. 직접 넣고 빼 보기

용량 8짜리 버퍼다. enqueue 는 head 위치에 값을 쓰고 head를 한 칸 전진, dequeue 는 tail 위치의 값을 꺼내고 tail을 한 칸 전진한다. 두 포인터가 배열 끝(7)을 지나면 0으로 감긴다.

가득 차면 덮어쓰기 (오래된 값 버림)

H = head(쓰기) · T = tail(읽기)

물리적 배열

size

head

tail

상태

비어 있음

3. "가득 참"과 "비어 있음"을 구별하는 문제

포인터만 보면 함정이 있다. 버퍼가 완전히 비었을 때도 head == tail, 완전히 찼을 때도 head == tail 이 된다. 같은 신호가 정반대 상황을 뜻하는 것이다. 흔한 해법 세 가지:

방법	내용
개수 세기	`size` 변수를 따로 둔다. `size == 0` 이면 empty, `size == capacity` 면 full. (이 데모가 쓰는 방식)
한 칸 비우기	칸 하나를 항상 낭비한다. `(head+1)%cap == tail` 이면 full로 간주. 변수 없이 포인터만으로 판별.
감기지 않은 인덱스	head·tail을 계속 증가시키고 접근할 때만 `% cap`. `head - tail` 이 곧 size, `== cap` 이면 full.

덮어쓰기 모드 — 위 데모에서 체크박스를 켜면, 가득 찬 상태에서 enqueue할 때 가장 오래된 값(tail)을 밀어내고 그 자리에 새 값을 쓴다. 최근 N개만 필요한 로그·센서 기록에서 이렇게 쓴다.

4. 어디에 쓰이나

오디오·비디오 스트리밍: 사운드 카드가 일정 속도로 버퍼를 소비하고, 디코더가 뒤에서 채운다 (생산자-소비자).
키보드 입력 버퍼: 프로그램이 바쁜 동안 눌린 키를 잠시 모아 둔다.
네트워크 카드(NIC)·시리얼 포트의 송수신 큐, OS 커널의 dmesg 링 로그.
최근 이벤트 기록: 항상 마지막 1000줄만 유지하는 로그 (덮어쓰기 모드).
락프리 큐: 생산자·소비자가 하나씩이면 포인터 하나씩만 건드려 락 없이 동기화가 된다.

5. 최소 구현

class RingBuffer:
    def __init__(self, capacity):
        self.buf = [None] * capacity
        self.cap = capacity
        self.head = 0      # 다음에 쓸 칸
        self.tail = 0      # 다음에 읽을 칸
        self.size = 0

    def enqueue(self, x):
        if self.size == self.cap:
            raise IndexError("buffer full")   # 또는 덮어쓰기
        self.buf[self.head] = x
        self.head = (self.head + 1) % self.cap
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("buffer empty")
        x = self.buf[self.tail]
        self.buf[self.tail] = None
        self.tail = (self.tail + 1) % self.cap
        self.size -= 1
        return x

파이썬 표준 라이브러리의 collections.deque(maxlen=N) 이 바로 덮어쓰기형 원형 버퍼다.

한 줄 요약 — 고정 배열 + 두 인덱스(head·tail) + % 용량. 데이터를 절대 옮기지 않고 넣기·빼기가 O(1). 끝이 처음으로 이어져 공간을 재활용하는, 스트리밍과 버퍼링의 기본 뼈대.