선형 큐를 사용하면 데이터를 꺼낼 때마다 앞부분에 빈 공간이 생기지만, 이를 활용하지 못해 공간이 낭비되는 문제가 발생한다.
이를 해결하기 위해 배열의 처음과 끝을 논리적으로 연결한 원형 큐(Circular Queue)의 구현 원리를 정리했다.
나머지 연산자(%)의 활용
원형 큐의 핵심은 인덱스가 배열의 끝에 도달했을 때 다시 0으로 돌아가게 만드는 것이다.
#define SIZE 5
int queue[SIZE];
int front = 0, rear = 0;
// 삽입 (Enqueue)
void enqueue(int data) {
if ((rear + 1) % SIZE == front) { // 포화 상태 체크
printf("Queue Full\n");
return;
}
rear = (rear + 1) % SIZE; // 인덱스 순환
queue[rear] = data;
}
// 삭제 (Dequeue)
int dequeue() {
if (front == rear) return -1; // 공백 상태 체크
front = (front + 1) % SIZE; // 인덱스 순환
return queue[front];
}
원형 큐의 상태 판별
- 공백 상태:
front == rear(머리와 꼬리가 같은 위치일 때) - 포화 상태:
(rear + 1) % SIZE == front(꼬리의 다음 칸이 머리일 때)
자원 재활용 효율성
원형 큐는 선형 큐처럼 데이터를 앞으로 이동시키는 작업 없이도 배열 공간을 재사용할 수 있다.
삽입과 삭제 모두 O(1)의 속도를 보장하며 공간 효율성도 높다.
자료구조 설계의 효율성을 확인할 수 있는 구조인 것 같다.
