원형 버퍼 (Circular Buffer, Ring Buffer)

원형 버퍼 (Circular Buffer, Ring Buffer)

고정 크기 배열을 순환 구조로 사용하는 FIFO 큐로, 끝에 도달하면 처음으로 돌아가며 읽기/쓰기 포인터로 관리하여 공간을 재사용

목적: 고정 크기 버퍼, 공간 재사용, 생산자-소비자 패턴, 실시간 스트리밍

특징: 고정 크기, 순환 구조, 덮어쓰기 가능, O(1) 연산, 락프리 가능

구성요소: ① 배열(고정 크기) ② 헤드(읽기 포인터) ③ 테일(쓰기 포인터) ④ 크기/용량

동작

• •enqueue: buffer[tail] = item, tail = (tail+1) % capacity
• •dequeue: item = buffer[head], head = (head+1) % capacity
• •Full: (tail+1) % capacity == head
• •Empty: head == tail

시간 복잡도: enqueue/dequeue 모두 O(1)

공간 복잡도: O(capacity) - 고정

장점: O(1) 연산, 공간 재사용, 캐시 효율, 락프리 구현 가능, 예측 가능한 메모리

단점: 고정 크기, 오버플로우 시 덮어쓰기 또는 에러, 용량 관리 필요

적용사례: 네트워크 패킷 버퍼, 오디오/비디오 스트리밍, 임베디드 시스템, 로그 버퍼, 생산자-소비자 큐

비교: 원형 버퍼(고정/빠름/순환) vs 동적 큐(가변/재할당/선형)

연관: 큐, 생산자-소비자, 락프리, 스트리밍