[알고리즘] 환형 큐(Circulation Queue)

환형 큐(Circulation Queue)

앞서 나왔던 큐의 포스팅이 너무 길어진 듯 해서 환형 큐는 따로 만들어 보았다.

환형 큐의 등장 배경은 다음과 같다.

큐의 head가 변함에 따라 기존에 사용하던 head index를 

쓰지 못하는 문제가 발생한다.

쉽게 말해, Dequeue를 해버리면 그자리는 다시 못쓰는 것이다.

이러한 문제점을 해결하기 위하여 환형 큐를 사용하게 되었다.

파워포인트로 그렸습니다ㅠ

이해가 잘되는 그림일지 모르겠지만 환형 큐의 구조는 다음과 같다.

head와 tail이 이동하여도 원형으로 순환(Circulation)하며 

같은 공간을 사용 할 수있으므로

기존의 큐보다는 효율적이라고 할 수 있다.

1. 환형 큐

int add(int num){
    if(tail==Q_Capacity){
        printf("Queue is Full!");
        return 0;
    }
    
    Q_size++;
    tail = (tail+1)%Q_Capacity;
    Q[tail] = num;
    
    return 0;
}
 
int del(){
    int del_data;
    
    if(tail<head){
        printf("There is no Data!");                                                                        
        return 0;
    }
    
    del_data = Q[head];
    head = (head+1)%Q_Capacity;
    Q_size—;
    
    return del_data;
}
Colored

구현하는 방법은 생각외로 굉장히 쉽다.

tail과 head의 값에 Queue의 용량을 고려해 주면된다.

기존에 하듯이 head와 tail을 연산이 끝난후 1증가 시키는것은 물론이고

용량이 초과되었을때를 고려하여 Q_Capacity 나누어진 나머지를 

head/tail로 설정한다.