원형 큐(circular queue)는 큐의 일종으로, 마지막 위치가 첫 번째 위치와 연결되어 원형 형태를 이루는 자료구조이다. 원형 큐는 배열을 사용하여 구현되며, 주로 고정된 크기의 배열을 사용한다. 일반적인 큐와 달리, 원형 큐는 공간을 효율적으로 사용한다.
특징
- 기본적인 큐의 처음과 끝을 논리적으로 연결하여 자료의 오버플로 문제를 해결하고, 저장 공간을 보다 효율적으로 사용할 수 있는 장점을 가진다.
- front와 rear의 초기값은 0이며, 자료가 입력될 때마다 rear 포인터가 한 칸씩 앞으로 이동하며 연산을 수행한다.
- 모든 공간이 자료로 가득 차면 front 포인터와 rear 포인터가 다시 같아져 포화 상태와 공백 상태를 구분할 수 없게 된다.
- 이 문제를 해결하기 위해 원형 큐의 마지막 한 자리는 항상 비워 두어야 한다.
- 최대로 저장할 수 있는 자료의 개수가 n개라면, rear 값이 front보다 1개 적은 시점, 즉 원소가 n-1개까지 입력할 수 있다.
삽입
- 새로운 자료를 삽입할 때는 먼저 원형 큐 내에 여유 공간이 있는지 확인해야 한다.
삭제
- 저장된 자료를 삭제할 때는 먼저 front와 rear의 값을 비교하여 공백 상태가 아닌지 확인해야 한다.
- 큐 안에 삭제할 원소가 남아 있으면 front를 1 증가시킨 후 해당 위치의 원소를 반환한다.