[자료구조] - Circular Queue (환형 큐)

 

 

 

배열로 구현한 Queue의 문제점

Queue는 배열로 구현하였을 때, 삽입과 삭제를 여러번 진행할 경우 배열의 위치가 점점 오른쪽으로 이동하게 됩니다.

 

즉 이렇게 구현하게 된다면, 붉게 표시된 배열의 빈 공간은 사용되지 않지만 메모리를 계속 차지함으로, 메모리 낭비를 발생시킵니다.

이를 해결하기 위한 방법으로 Circular Queue를 사용합니다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

Circular Array Queue

기존의 Queue와 대부분 비슷하지만, 배열의 끝이 배열의 처음과 붙어 있는 것으로 생각합니다.

즉 다음과 같은 반지 형태를 생각하시면 이해하기 좋습니다.

 

 

 

 

 

 

 

 

 

Circular Queue의 삽입과 삭제

1개 삽입

 

7개 삽입

 

1개 제거

 

1개 추가

 

2개 더 추가

 

즉 위와 같이 Circular Queue를 사용하면 배열의 모든 공간을 효율적으로 사용할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

배열로 구현한 Circular Queue의 용량과 배열의 최대 길이의 관계

Circular Queue를 사용하면 배열이 가득 찼는지, 아니면 비어있는 상태인지를 파악하기 어렵습니다.

 

쉬운 예시를 위해 삭제가 발생하지 않고, 오로지 삽입만 발생하는 용량(capacity) 3의 Circular Queue를 생각해 보겠습니다.

 

 

배열에 모든 원소를 삽입한 경우 rear은 다시 초기 상태로 돌아갑니다.

즉 초기 상태의 경우 front == rear이기 때문에 비어있는 상태이지만,

배열이 가득 찬 경우에도 front == rear입니다.

 

 

이를 해결하기 위해 Circular Queue에서는 배열의 마지막 칸을 사용하지 않습니다.

따라서 Queue와 동일한 용량을 저장하기 위해서는, 배열의 크기를 capacity + 1로 해주어야 합니다.

 

가득 찼는지의 여부는 rear의 다음 위치를, Circular Queue의 배열의 길이, 즉 용량 + 1로 나눈 나머지가 front와 동일한지를 검사하면 됩니다.

 

 

 

 

정리하자면 Circular Queue에 저장하고 싶은 원소의 최대 개수를 capacity라고 하면, 배열의 길이는 이보다 1 커야 합니다.

즉 배열의 길이를 maxLength라 정의하면 다음과 같습니다.

this.maxLength = this.capacity + 1;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

다음 위치 계산법

기존 Queue에서는 단지 rear를 1만 증가시켜주면 되었습니다.

그러나 환형 큐에서는 추가적인 작업이 필요한데,

rear을 1 증가시켰을 때 rear의 크기가 배열의 최대 길이와 동일하다면 rear을 0으로 바꾸어 주어야 합니다.

 

즉 다음과 같습니다.

this.rearIdx = (this.rearIdx + 1) % this.maxLength;

 

 

 

 

 

 

 

 

 

 

초기화 방법

기본 큐와 같이 rear과 front를 0으로 설정하면 됩니다.

this.frontIdx = 0;
this.rearIdx = 0;

 

 

 

 

 

 

 

 

Empty 조건

기존 Queue와 동일하게 front와 rear의 위치가 동일하다면 비었다고 판단합니다.

this.frontIdx == this.rearIdx;

 

 

 

 

 

 

 

 

 

 

 

Full 조건

위에서 살펴보았듯이 배열의 최대 길이에서, 1개가 덜 찬 상태를 Full로 생각합니다.

즉 다음과 같이 rear에 1개를 더했을 때, 해당 위치가 front와 같으면 가득 찬 상태입니다.

((this.rearIdx + 1) % this.maxLength) == this.frontIdx;

 

 

 

 

 

 

 

 

 

자바로 구현

https://ttl-blog.tistory.com/697

[Java] - 자바로 Circular Queue 구현하기