배열 기반 원형 큐(Ring Buffer) — front·back 인덱스로 만드는 큐
NOTE
malloc/free를 반복하지 않고, 고정 크기 배열 하나로 FIFO 큐를 만드는 원형 큐(circular queue, ring buffer) 패턴을 정리한다. 인덱스 두 개만으로 push/pop을 O(1)에 처리하는 방법과, 그 과정에서 항상 걸리는 “가득 참 vs 빔” 구분 문제를 다룬다.
0. 왜 필요한가
연결 리스트로 큐를 만들면 노드를 넣을 때마다 malloc, 뺄 때마다 free를 호출해야 한다. 요청이 초당 수천 번 들어오는 경로라면 이 할당/해제 비용과 메모리 단편화가 무시하기 어려워진다. 큐에 담을 수 있는 최대 개수를 미리 알 수 있다면, 배열 하나를 고정 크기로 잡아두고 그 위에서 앞/뒤 위치만 인덱스로 관리하는 게 훨씬 싸다 — 이게 원형 큐다.
1. 기본 구조 — 배열 + 두 개의 인덱스 + 개수
typedef struct {
int buf[8]; /* 고정 크기 저장 공간 */
int max_cnt; /* 저장 가능한 최대 개수 */
int cur_cnt; /* 현재 들어있는 개수 */
int front_idx; /* 다음에 꺼낼 위치 */
int back_idx; /* 다음에 넣을 위치 */
} ring_queue_t;
void ring_queue_init(ring_queue_t *q)
{
q->max_cnt = 8;
q->cur_cnt = 0;
q->front_idx = 0;
q->back_idx = 0;
}“원형”이라 불리는 이유는 back_idx가 배열 끝에 닿으면 다시 0으로 되돌아가서, 배열을 마치 끝과 끝이 이어진 원처럼 순환하며 재사용하기 때문이다.
2. push — 뒤에 채우고, 끝에 닿으면 되감기(wraparound)
int ring_queue_push(ring_queue_t *q, int value)
{
if (q->cur_cnt >= q->max_cnt) {
return -1; /* 가득 참 */
}
q->buf[q->back_idx] = value;
q->back_idx++;
if (q->back_idx >= q->max_cnt) {
q->back_idx = 0; /* 배열 끝에 닿으면 처음으로 되감기 */
}
q->cur_cnt++;
return 0;
}back_idx++만 하고 끝나면 배열 범위를 벗어나므로, 매번 증가시킨 뒤 max_cnt에 닿았는지 확인해서 0으로 되돌리는 것이 원형 큐의 핵심 동작이다. q->back_idx = (q->back_idx + 1) % q->max_cnt;처럼 나머지 연산자(%)로 한 줄에 처리할 수도 있다 — 동작은 같지만, 나눗셈 연산이 들어가는 만큼 if문보다 약간 느릴 수 있어 실무에서는 두 방식이 섞여 쓰인다.
3. pop — 앞에서 꺼내고, 끝에 닿으면 마찬가지로 되감기
int ring_queue_pop(ring_queue_t *q, int *out_value)
{
if (q->cur_cnt <= 0) {
return -1; /* 비어있음 */
}
*out_value = q->buf[q->front_idx];
q->front_idx++;
if (q->front_idx >= q->max_cnt) {
q->front_idx = 0;
}
q->cur_cnt--;
return 0;
}push가 back_idx만 건드리고 pop이 front_idx만 건드린다는 점에 주목한다 — 두 인덱스는 서로 독립적으로 앞으로만 나아가며, 배열 위를 도넛처럼 계속 돌 뿐이다.
4. 왜 인덱스 비교만으로는 “가득 참”과 “빔”을 구분할 수 없는가
cur_cnt라는 카운터 필드 없이 front_idx와 back_idx만으로 상태를 판단하려 하면 문제가 생긴다.
if (front_idx == back_idx) {
/* 이게 "완전히 비어있다"는 뜻인가, "완전히 가득 찼다"는 뜻인가? */
}큐가 갓 초기화돼서 front_idx == back_idx == 0인 상태(빔)와, push를 계속해서 한 바퀴를 다 돌아 다시 front_idx == back_idx가 된 상태(가득 참)가 인덱스 값만으로는 구분이 안 된다. 이 문제를 푸는 방법은 크게 두 가지다.
| 해법 | 방식 | 장단점 |
|---|---|---|
| 개수 필드 추가 (이 노트의 방식) | cur_cnt를 따로 두고 push/pop마다 증감 | 배열 슬롯을 전부 다 쓸 수 있다. 필드 하나가 더 필요할 뿐 |
| 자리 하나를 일부러 비워둠 | 배열을 max_cnt + 1칸으로 잡고, (back_idx + 1) % size == front_idx를 “가득 참”으로 정의 | 추가 필드가 없어도 되지만, 실제로 쓸 수 있는 칸이 하나 줄어든다 |
어느 쪽이든 인덱스 두 개만으로는 부족하고, 상태를 구분할 추가 정보(개수 또는 여분 슬롯)가 반드시 필요하다는 결론은 같다.
5. 자주 하는 실수
back_idx/front_idx되감기(wraparound)를 깜빡하기 — 배열 끝에 닿았는데 0으로 되돌리는 코드를 빼먹으면 배열 밖 메모리에 쓰거나 읽는다. push/pop 양쪽 다 증가 직후 반드시 범위 체크를 넣는다.cur_cnt갱신을 깜빡하거나 push/pop 중 한쪽에서만 갱신하기 — push는 증가, pop은 감소를 매번 짝지어야 한다. 하나라도 빠지면 실제 상태와cur_cnt가 어긋나서, 가득 찼는데 빈 걸로 착각하고 계속 넣거나 반대로 멀쩡한데 가득 찼다고 오판하게 된다.- 여러 스레드가 동시에 push/pop을 부르는데 락이 없기 —
cur_cnt++/cur_cnt--는 원자적 연산이 아니다(자세한 내용: 락 없는 카운터). 큐를 여러 스레드가 공유한다면 push/pop 구간을 뮤텍스로 감싸거나, 생산자-소비자가 각각 하나씩인 특수한 경우가 아니라면 반드시 동기화가 필요하다. max_cnt를 0 또는 음수로 잘못 설정하고 시작하기 — 초기화 시점에 크기 검증 없이 그대로 쓰면cur_cnt >= max_cnt조건이 항상 참이 되어 아무것도 못 넣거나, 반대로 배열 크기를 벗어난 접근이 발생한다.