[자료구조]원형 큐(Circular Queue) - 개선

그림을...그렸는데.... 오류때문에 열리지않아,,
text로 임시로 씁니다...

원형 큐를 활용하여 앞선 큐의 단점을 보완할 수 있는데
원형 큐에서도 생각할것이 하나 더 있다.
그것은 바로 큐가 완전 비어져있을때와 꽉 차 있을때 R 다음 F인 같은 형식을 띠고 있어서 차이점을 못 느낀다는 것인데
이것의 해결방법은
생각외로 간단하다 !!

바로 !!! 배열을 꽉 채우지 않는것이다 !

즉, 배열의 길이가 N이라면 N-1개가 채워져있을 떄, 이를 꽉 찬 것으로 간주하는것이다.
이렇게 하면 저장 공간 하나를 낭비하게 되지만, 이로 인해서 문제가 해결되는 셈이니 잃는 것보다 얻는 것이 더 크다 !
F와R은 계속해서 회전하니 F와 R의 상대적인 위치를 통해서 텅 빈 경우와 꽉 찬 경우를 구분해야한다.

이렇게 하여 만들어진 개선된 원형 큐의

enqueue연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에 ,R이 가리키는 위치에 데이터를 저장한다.
dequeue연산 시, F가 가리키는 위치를 한칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반한 및 소멸 한다.

이로서
앞의 문제점 원형 큐가 텅 빈 상태와 꽉 상태에서 f 와 r의 상대적 위치가 동일했던 문제점을 해결 할 수 있다 !

• 원형 큐가 텅 빈 상태 : F와 R이 동일한 위치를 가리킨다.
• 원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다.