[Python] 링 버퍼 (Ring buffer) 와 원형 큐

고정된 크기의 메모리 공간(버퍼)을 순환적으로 사용하는 자료구조. 배열의 끝에 도달하면 다시 시작위치로 돌아가서 데이터를 저장하거나 읽는 방식

주요 특성

• 고정 크기 메모리 사용
  미리 정해진 크기의 배열(버퍼)을 사용함
  동적 크기 조절 없이 항상 일정한 메모리 사용
• 순환적 구조 (원형 구조)
  배열의 끝에 도달하면, 다음 요소는 배열의 첫 번째 위치부터 기록됨
  인덱스 관리 시 모듈로(%) 연산 사용하여 wrap-around 처리
• 빠른 데이터 접근
  인덱스 계산만으로 삽입과 삭제 연산(O(1))을 수행함
  실시간 데이터 스트림 처리나 버퍼링에 적합
• FIFO 원칙 적용
  기본적으로 큐와 같은 선입선출(FIFO) 특성을 따름
  데이터를 넣은 순서대로 읽어내거나 제거함

구성 요소

• 버퍼 (배열): 데이터를 저장할 고정 크기의 배열
• front (읽기 포인터): 데이터 제거 또는 읽기가 이루어지는 위치를 가리킴
• rear (쓰기 포인터): 새 데이터를 삽입하는 위치를 가리킴
• size (현재 데이터 개수): 현재 버퍼에 저장된 데이터의 수를 나타냄

동작 원리

1. 데이터 삽입 (enqueue)
   • rear 위치에 데이터를 저장함
   • 삽입 후, rear를 (rear + 1) % capacity 로 업데이트하여 순환 처리
   • 버퍼가 꽉 찼다면 삽입 불가 (또는 오버라이트 정책 적용 가능)
2. 데이터 삭제 (dequeue)
   • front 위치의 데이터를 읽고 제거함
   • 제거 후, front를 (front + 1) % capacity 로 업데이트
   • FIFO 순서를 유지하여 먼저 들어온 데이터가 먼저 삭제됨

장단점

• 장점
  • 고정된 메모리 사용으로 사용량을 예측 가능
    • 일반 배열이나 동적 리스트처럼 런타임에 메모리 확장이 일어나지 않아, 실시간 응답에 좋음
    • 예시 : 임베디드 시스템에서 메모리 할당을 미리 정해 둔 상태로 관리해야 할 때 유리
  • 단순한 구현과 빠른 연산 - O(1)
    • 연결 리스트의 경우 노드 할당/해제 비용이 추가
    • 삽입과 삭제가 항상 상수 시간에 처리됨
    • 인덱스 계산 시 모듈로 연산만 사용해서 성능이 일정함
  • 캐시 효율성
    • 고정된 크기의 연속된 메모리 공간만 사용
    • CPU 캐시 적중률이 높아서 데이터 접근 속도가 빠름
    • 연결 리스트는 노드들이 메모리 상 흩어져있어 캐시 효율이 떨어짐

캐시 적중률이란?
CPU가 데이터를 요청할 때, 필요한 데이터가 캐시 메모리 내에 이미 존재해서 빠르게 접근할 수 있는 경우의 비율을 말함.
예를 들어, 100번의 메모리 접근 중 90번을 바로 찾는다면, 적중률은 90%가 됨. 높을 수록 전체 시스템 성능이 좋아짐

• 단점
  • 버퍼 크기가 고정되어 있어 크기를 초과하는 데이터는 처리 불가
    • 동적 배열이나 연결 리스트는 필요에 따라 크기 조절
  • 꽉 찬 상태와 빈 상태를 구분하기 위한 추가 관리 필요
    • front와 rear의 관계나 별도의 플래그가 필요
    • 잘못 관리하면 상태를 혼동할 수 있음

다른 자료구조와 비교

• 동적 배열
  동적 배열은 크기 조절이 가능함. 삽입 시 배열 확장이 일어나면 시간 복잡도는 O(n)이 될 수 있음
  반면 원형 큐는 고정 크기이기 때문에 항상 O(1) 연산을 보장하지만, 크기 제한이 있음
• 연결 리스트
  연결 리스트는 노드 할당으로 동적 크기 조절이 자유롭고 삽입/삭제 연산이 O(1)임
  그러나, 각 노드가 메모리 상에 분산되어 있어서 포인터 관리 오버헤드와 낮은 캐시 효율 문제가 있음
  원형 큐는 연속된 메모리 공간을 사용하므로 캐시 성능이 우수함
• 덱(Deque)
  덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조임
  인터페이스가 좀 더 풍부하고, 다양한 상황에 대응할 수 있음
  원형 큐는 기본적으로 FIFO(선입선출)에 집중되어 있어 인터페이스가 단순함

링버퍼와 원형 큐

그래서 뭐가 다른건데?

결론만 이야기하면, 원형 큐는 큐의 추상적 동작 (FIFO)을 보장하는 데이터 구조 개념이고, 링버퍼는 이를 구현하는 구체적 방법
(원형 큐를 구현하는 다른 방법으로는 원형 연결리스트, 덱(deque)이 있음)
세부적으로 따지면 아래 몇가지가 있는데 ‘그냥 이런거구나’ 하고 훑어가는 정도면 될 것 같다.

• 용어의 맥락
  • 원형 큐는 주로 추상 자료구조로, FIFO 동작을 명세하는데 사용
  • 링버퍼는 저수준 구현체나 임베디드 시스템, 실시간 시스템(RTOS)에서 주로 사용 (Circular buffuer 라고도 함)
• 동작
  • 원형 큐는 일반적으로 꽉 찼을 때 삽입을 거부하는 방식으로 동작
  • 일부 링버퍼는 꽉 찼을 때 새로운 데이터를 넣으면 기존 데이터를 덮어쓰는(overwrite) 방식을 채택함
• 응용 분야
  • 원형 큐는 주로 자료구조 학습이나 알고리즘 문제에서 FIFO 특성을 구현할 때 사용
  • 링버퍼는 실시간 데이터 스트림 처리, 오디오/비디오 버퍼링 등에서 효율적인 메모리 사용과 빠른 데이터 접근을 위해 사용

링버퍼로 원형 큐 구현

여기 16의 크기를 가진 큐를 만들기 위해 전역 변수들을 선언한다

• capacity: 큐의 최대 크기를 16으로 고정
• queue: 16개의 요소로 구성된 고정 크기 배열(리스트), 처음에는 모든 요소가 None

capacity = 16              # 큐의 최대 크기
queue = [None] * capacity  # 고정 크기 배열 (리스트)

원형큐는 큐의 FIFO 원칙에 따라 front와 rear 순서에 맞게 삽입/삭제를 해야하고,
순환하는 구조를 위해 배열의 위치가 물리적인 앞과 뒤가 아닌 논리적인 순서를 가져야하므로,
인덱스 형태로 front와 rear를 관리해주어야함

그래서 초기값 front, rear 인덱스와, 배열 내 데이터 개수도 초기에 선언해줌

front = 0                  # 데이터 삭제(읽기) 포인터, 초기값 0
rear = 0                   # 데이터 삽입 포인터, 초기값 0
size = 0                   # 현재 저장된 데이터 개수

큐의 뒤쪽(rear)에 새 데이터를 삽입하는 연산인, 인큐(enqueue)를 구현

큐가 꽉 찼는지 검증 후, rear index를 통해 데이터를 바꿔줌.

이후 rear 포인터는 한칸 올려준다. (이때 % 연산으로 나머지연산을 하면 다음칸을 쉽게 구할 수 있다)

def enqueue(x: any) -> None:
    global queue, rear, size, capacity
    if size == capacity:
        raise IndexError("Queue is full")  # 큐가 꽉 찬 상태
    queue[rear] = x                    # 현재 rear 위치에 데이터 삽입
    rear = (rear + 1) % capacity       # rear 포인터를 원형으로 업데이트
    size += 1                          # 데이터 개수 증가

• 동작 과정:
  1. 꽉 찼는지 검사: size가 capacity와 같으면 큐가 꽉 찬 상태이므로 삽입 불가
  2. 데이터 삽입: 현재 rear 위치에 데이터를 저장
  3. rear 포인터 업데이트: (rear + 1)을 capacity로 나눈 나머지로 계산하여 원형 구조를 유지
  4. 저장된 데이터 개수 증가: size 값을 1 증가

• 모듈러 (%) 연산을 통해 다음 인덱스를 구하기
  원형 큐에서는 인덱스가 배열의 크기를 초과하면 0으로 돌아가기 위해 사용되는데, 기본 공식은 다음과 같다
  next_index = (current_index + 1) % capacity
  • 예를 들어, 현재 인덱스가 4라면 next_index = (4 + 1) % 16 = 5 % 16 = 5
    다음 인덱스는 5가 주어짐(+1과 동일하게 결과도출)
  • 만일 현재 인덱스가 15(배열 크기의 끝)라면,
    next_index = (15 + 1) % 16 = 16 % 16 = 0 배열의 끝에 도달 시 0번 인덱스로 돌아감.

큐의 데이터를 가져(삭제 또는 읽기)오는 dequeue를 구현

def dequeue() -> any:
    global queue, front, size, capacity
    if size == 0:
        raise IndexError("Queue is empty")  # 큐가 비어 있음
    x = queue[front]                   # front 위치의 데이터 저장
    queue[front] = None                # 삭제한 위치를 None으로 초기화
    front = (front + 1) % capacity     # front 포인터를 원형으로 업데이트
    size -= 1                          # 데이터 개수 감소
    return x                           # 삭제된 데이터 반환

• 동작 과정:
  1. 비어있는지 검사: size가 0이면 큐가 비어 있으므로 삭제 불가
  2. 데이터 읽기: 현재 front 위치의 데이터를 임시 변수에 저장
  3. 해당 위치 초기화: 삭제한 위치에 None을 대입 (선택적 처리)
  4. front 포인터 업데이트: (front + 1)을 capacity로 나눈 나머지로 계산하여 순환 처리
  5. 저장된 데이터 개수 감소: size 값을 1 감소
  6. 저장된 데이터 반환: 임시 변수에 저장된 데이터를 반환