원형 큐(Circular Queue)

이번에는 이전 큐의 단점을 보완한 원형큐를 구현하되

일정 할당량을 넘게되면 계속해서 새로운 할당을 받아 계속 add할 수 있게

하는 큐를 구현해보았다.

 

원형 큐

 

원형큐는 front  = rear 일때 완전히 비어있음을 의미하게 되고,

front = rear+1 이 되는 순간 꽉차있는 것을 의미한다. 

front와 rear사이에는 하나의 공간이 비어있게되는데, 이는 큐가 비어있음과 꽉차있음을 구분하기 위해서이다.

 

Circular Queues Using Dynamically Allocated Arrays

 

원형큐를 사용하다보면 윗그림과 같은 경우가 발생한다. 이때, 큐를 동적할당으로 capacity를 늘려주고, front와 rear를 newQueue 를 사용해 다시한번 정리하게 된다.

 

 

 

 

 

코드를보면 다 똑같은데 COPY부분이 이해하기 어렵다.

단순히 front와 rear를 정리하는것인데, 배열 시작점과 끝점을 인자값으로 줘야해서 헷갈린다.

 

 

선입선출형태의 큐구조. 단, capacity allocation을 확인할수 있다.