순환 큐 (Circle Queue)

Que

 

Que는 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 자료구조이다.

 

Que를 사용하는 이유는 밀려드는 데이터를 '보관할 장소'로 큐가 필요한 것이다.

 

큐의 주요 기능

 

1. 삽입과 제거

 

큐의 가장 앞 요소를 전단(Front), 가장 뒤의 요소를 후단(Rear)라고 부른다.

 

 

큐는 삽입(Enqueue)는 후단(Rear), 삭제(Dequeue)는 전단(Front)에서 수행된다.

 

위 그림처럼 전단을 제거한 후 나머지 요소들을 한 칸씩 앞으로 옮길 때 1을 삭제하면

배열의 인덱스가 비게되는데 빈 배열의 인덱스를 채우기 위해서 뒤에 있떤 2,3,4,5,6,7을

한 칸씩 앞으로 옮기게 되면 성능상 많은 비효율적인 문제가 발생하게 된다.

 

이 문제를 해결하기 위해서 전단을 가리키는 변수를 도입해서 배열 내의 인덱스를 옮기는 것

대신에 전단의 위치만 관리하는 것이 효율적인데, 후단도 이와 같은 방법으로 관리를 하면된다.

후단은 후단을 가리키는 위치에 +1을 한 값을 가지면 된다.

 

하지만 이렇게 삭제를 반복하게되면 큐의 가용 용량도 줄어들게 되는데 이 문제는

큐 배열을 만들 때 실제의 용량보다 +1만큼 더 크게 만들어서 전단과 후단(실제의 후단) 사이를

비우게 하는 것이다.

이렇게 하면 큐가 비어있을 때는 전단과 후단이 같은 곳을 가리키게 되고, 큐가 차 있을 때는

후단이 전단보다 -1 작은 값을 갖게 되는 것이다.

 

또한 배열이 실제 데이터가 담길 공간보다 +1만큼 큰 이유는 순환 큐가 공백인지 포화상태인지

구분하기위한 더미 노드가 필요하기 때문이다.

 

큐가 비어있거나 가득 차 있을 때

 

- Circle Queue는 비어 있는 상태와 가득 차 있는 상태를 구분할 수 없다.

- 큐를 구현할 때 후단은 실제 후단에서 +1을 한 값이다. !!!!!!!!!!!!!! 중요