원형 큐 (Circular Queue)

큐 구현의 문제점은 계속 rear에 원소를 추가하게 되면 위의 사진처럼 길이 10짜리 배열을 선언하고 

큐의 크기를 4짜리를 사용하다 보면 배열의 크기를 벗어나게 되면 앞의 공간이 비게 되어 

공간의 효율성이 매우 떨어진다.

공간의 효율성이 떨어지는 큐를 개선한 원형 큐 (Circular Queue)는

 front와 rear을 연결하여 그림과 같이 공간을 효율적으로 사용할 수 있다.

data 배열의 길이를 8로 선언하고, 길이가 4인 원형 큐를 구현하는 방법을 보자.

rear 에 원소를 계속 추가하다 보면 data 가 꽉차게 되는데

이때 rear을 다시 0으로 바꾸는 것이다. 그러면 비어있는 앞의 공간을 활용할 수 있다.

front 역시 배열의 끝까지 도달하게 되면

다시 0으로 front를 옮겨주어 공간 활용을 한다.

원형 큐를 구현할 때 주의해야할 점은 큐의 크기를 구할때 선형 큐에서는 rear에서 front를 빼서 

현재 들어가 있는 원소의 개수를 구했지만

원형 큐에서는 front와 rear가 0부터 다시 가기 때문에, 따로 변수를 정해서 

원소를 삽입(push) 할 때 마다 변수를 증가시키고 원소를 삭제(pop) 할 때 마다 변수를 감소 시켜야 한다.

출처 : AlgorithmLABS