순환 큐는 마지막 요소가 첫 번쨰 요소에 연결되는 일반 큐 의 확장 버전이다.
위와 같이 원고 같은 구조를 형성하게 된다.
순환 큐는 일반 큐의 주요 제한 사항을 해결하는데, 일반 큐에서는 삽입과 삭제 후에 사용할 수 없는 빈 공간이 생긴다.
여기서 인덱스 0, 1 은 큐를 재설정(모든요소삭제)한 후에만 사용할 수 있다.
이렇게 하면 대기열의 실제 크기가 줄어들게된다.
순환 큐 작동방식
일반 큐는 FIFO 의 입출력이 되는 선형자료 구조인데. 먼저 입력된 값이 먼저 출력되는 구조이다.
일반적인 선형 큐는 출력을 담당하는 Front와 입력을 담당하는 Rear 두가지 공간으로 입출력이 일어난다.
그렇다면 순환 큐는?
먼저 위에 그림을 설명하자면,
1,2,3,4,5 라는 데이터가 큐에 다 입력되면 Front는 1, rear은 5를 가리키게 되는데,
1,2가 먼저 들어온 데이터이니 만큼 먼저 나가게 된다. 그렇게 되면 일반 큐는 그 공간을 사용하지 못하게 되어 메모리 낭비가 일어나게 되는데 순환큐는 다르다.
순환큐에서는 나간 1 자리에(비어있는 첫번째 인덱스) 6을 다시 삽입할 수 있다.
이렇게 되면 rear은 5를 가리키는게 아닌 마지막에 들어온 6을 가리키게 된다.
삽입과 삭제 과정:
- 삽입은 Rear가 가르키는 다음 공간으로 이동하여 값을 넣는다.
- 삭제는 Front가 가르키는 다음 공간으로 이동하여 값을 제한다.
- 비어있을 경우는 두 포인터가 같은 공간을 가르킬 경우이다.
- 모두 차있을 경우는 Rear의 다음 공간이 Front일 경우이다.
단, 단순히 로직을 구현했을 때, 비어있을 경우와 모두 차있을 경우 모두 Front와 Rear가 같은 공간을 가르켜 구분이 가지 않는다. 이를 위해, 한 공간을 비워두고 표현하게 된다.
