원형큐

선형큐는 front 와 rear 의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지 못한다는 점이 단점이다. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 한다. 하지만 이런 식으로 요소들을 이동시키면 상당한 시간과 코딩이 복잡해진다. 이러한 문제는 배열을 선형으로 생각하지 말고 원형으로 생각하면 쉽게 해결된다. 즉, front 와 rear 의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다. 즉 다음과 같이 배열이 원형으로 처음과 끝이 연결되어 있다고 생각하는 것이다. 여기서 실제 배열이 원형으로 변화되는 것은 아니다. 그냥 개념상으로 원형으로 배열의 인덱스를 변화시켜주는 것 뿐이다.

 

원형큐에서는 front 와 rear 의 개념이 약간 변경된다. 먼저 초기값은 -1 이 아닌 0 이다. 또 front 는 항상 큐의 첫 번째 요소의 하나 앞을, rear 는 마지막 요소를 가리킨다. 처음에 front, rear 는 모두 0이고 삽입 시에는 rear 가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입된다. 또 삭제 시에는 front 가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제한다. 이런 식으로 생각하면 된다.

 

front 와 rear 의 값이 같으면 원형 큐가 비어 있음을 나타낸다. 원형큐에서는 하나의 자리는 항상 비워둔다. 왜냐하면 포화 상태와 공백 상태를 구별하기 위해서이다. 만약 한 자리를 비워두지 않는다면 공백상태와 포화상태를 구분할 수 없을 것이다. 따라서 원형큐에서 fromt == rear 이면 공백 상태가 되고 만약 front가 rear 보다 하나 앞에 있으면 포화 상태가 된다. 만약 요소들의 개수를 저장하고 있는 추가적인 변수 count 변수를 사용할 수 있다면 한 자리를 비워두지 않아도 된다.