원형 큐(Circular Queue) 제작

큐는 데이터를 삽입할 때 뒤쪽인 tail 쪽에 삽입을 하고 읽을 땐 head부터 읽는 FIFO(First In First Out) 구조의 자료형이다.

이와 같은 구조의 큐를 선형 큐라고 한다. 선형 큐는 데이터를 삭제(pop)할 때마다 head가 뒤로 밀려 앞에 공간이 남아있음에도 불구하고 데이터를 삽입할 수 없는 문제가 발생한다.

[출처] 원형큐|작성자 since860321

이러한 큐의 단점을 개선한 것이 원형 큐이다.

이 가득찬 원형 배열의 데이터를 차례대로 읽은 후, 데이터를 삽입을 하려고 한다면 다시 1의 자리에부터 데이터가 채워지게 구현을 하면 될 것이다.

bool push( const T& data ) 
{ 
    ... 

    if( tail == 배열의 크기 )  
    { 
        tail = 배열의 처음; 
    } 

    ... 
}