[자료구조] 순환 큐(Circular Queue) - 코딩밥상

배열 기반 순환 큐

배열을 기반으로 선입선출의 방식을 따르는 큐를 구현한다고 생각해 봅시다.

제거 연산 후에 전단 요소가 삭제 된다면 남아있는 모든 요소들은 빈 자리를 채우기 위해 앞으로 당겨야 합니다. 이는 엄청난 비용을 필요로 합니다. 그렇다면 전단을 가리키는 변수를 도입해서 배열 내 요소들을 옮기는 대신 전안의 위치만 변경하면 어떻게 될까요? 그 전처럼 불필요한 비용은 발생하지 않지만, 배열의 크기는 생성과 함께 고정되기때문에 삽입과 연산이 반복될수록 사용가능한 배열의 공간은 점차 작아지다가 결국 사용 불가능해지겠네요...

이러한 복잡한 문제를 해결하기 위해 이 책에서는 고대 로마 철학자인 세네카가 남긴 명언을 제시합니다.

"모든 시작은 또 다른 시작의 끝으로부터 비롯된다."

 

즉 배열의 끝과 시작을 연결합니다. 그렇게되면 공간을 희생하지 않고도 삽입과 삭제 연산을 수행 할 수 있습니다.

여기서 또 하나 알고 가야 할 개념이 있습니다. 삽입을 한 후에 큐의 전단과 후단이 만나면 그 큐는 '가득 찬 상태'가 됩니다. 더 이상 삽입 될 공간이 없는것이죠. 이 상태에서는 삭제가 일어나지 않는 이상 추가적인 삽입은 불가능합니다.

 

본격적인 구현 전에 신경써야 할 부분이 한가지 더 있습니다. 큐가 포화 상태일 때뿐 아니라 공백상태일 때도 전단과 후단이 만나기 때문에 이 두 상태를 구분해야합니다.

그 방법은 실제 값이 없는 노드 더미를 하나 추가로 만들어 줍니다. 큐 배열을 생성할 때 실제 용량보다 하나 더 크게 만들어 전단과 후단 사이를 한칸 비우는 것입니다.

이렇게 하면 큐가 공백상태일 때 전단과 후단이 같은 곳을 가리키고, 큐가 포화상태일 때는 후단이 전단보다 한칸 다른칸을 가리키므로 상태 구분을 할 수 있어집니다.

 

---

코드 구현

-노드와 순환 큐의 구조체

typedef int ElementType;

typedef struct tagNode{ //노드 구조체
    ElementType Data;
} Node;

typedef struct tagCircularQueue{   //순환 큐 구조체
    int Capacity;
    int Front;
    int Rear;
    
    Node* Nodes;
} CircularQueue;

-순환 큐의 생성과 소멸

void CQ_CreateQueue(CircularQueue** Queue, int Capacity){   //Heap에 순환 큐 할당(큐 생성)
    (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
    (*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1));	//더미 노드도 생성해줌
    
    (*Queue)->Capacity = Capacity;
    (*Queue)->Front = 0;
    (*Queue)->Rear = 0;
}

void CQ_DestroyQueue(CircularQueue* Queue){ //Heap에 할당되어있던 큐 해제(큐 소멸)
    free(Queue->Nodes);
    free(Queue);
}

-순환 큐의 삽입(Enqueue)

void CQ_Enqueue(CircularQueue* Queue, ElementType Data){    //삽입 연산(Enqueue)
    int Position = 0;
    
    if(Queue->Rear == Queue->Capacity){     //순환 구조(끝 노드의 다음 노드는 첫 노드)
        Position = Queue->Rear;
        Queue->Rear = 0;
    }
    else{
        Position = Queue->Rear++;
    }
    
    Queue->Nodes[Position].Data = Data;
}

-순환 큐의 제거(Dequeue)

ElementType CQ_Dequeue(CircularQueue* Queue){   //삭제 연산(Dequeue)
    int Position = Queue->Front;
    
    if(Queue->Front == Queue->Capacity){    //순환 구조(끝 노드의 다음 노드는 첫 노드)
        Queue->Front = 0;
    }
    else{
        Queue->Front++;
    }
    
    return Queue->Nodes[Position].Data;
}

-그 외 연산들( IsEmpty(), IsFull(), GetSize() )

int CQ_IsEmpty(CircularQueue* Queue){   //공백 상태 확인
    return (Queue->Front == Queue->Rear);
}

int CQ_IsFull(CircularQueue* Queue){    //포화 상태 확인
    if(Queue->Front < Queue->Rear){ //후단이 전단 뒤에 있을 때
        return (Queue->Rear - Queue->Front) == Queue->Capacity;
    }
    else{   //전단이 후단 뒤에 있을 때
        return (Queue->Rear + 1) == Queue->Front;
    }
}

int CQ_GetSize(CircularQueue* Queue){   //크기 반환
    if(Queue->Front <= Queue->Rear)
        return Queue->Rear - Queue->Front;
    else
        return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;
}