자료구조 - 순환 큐(Circular Queue)

큐(Queue)란 먼저 들어간 데이터가 먼저 나오는(FIFO, First In First Out) 자료구조형이다.

 

스택은 한쪽에서만 데이터를 삽입하고 제거하지만,

큐(Queue)는 데이터를 후단(Back)에서 삽입을(Enqueue) 하고 전단(Front)에서 제거(Dequeue)를 한다. 

한마디로 스택은 입만 있어서 입으로만 먹고 뱉는데

큐는 입이랑 엉덩이가 있다는 소리이다(엉덩이로 먹고 입으로 뱉고 있지만)

 

먼저 큐를 구현할 때도 스택을 구현할 때처럼

배열로 구현할 수 있고, 링크드 리스트로 구현할 수 있다.

 

먼저 배열로 큐를 구현할 때를 생각해보자.

 

배열의 특성상 큐의 용량(Capacity) 이미 정해져 있으므로,

배열로 구현한 큐의 삽입(Enqueue)과 삭제(Dequeue)의 함수 구현에는 주의해야 할 2가지 사항이 있다.

 

첫번째로 삽입과 삭제가 이루어진 후 큐의 상태를 어떻게 처리 할 것인거다.

 

용량(Capacity)이 5 이고 이미 데이터가 1, 2, 3, 4가 들어있는 큐로 생각해보자.

Dequeue(1) =>

Enqueue(5) =>

Dequeue(2) =>

Enqueue(6) =>

지금 구현한 큐는 삽입, 삭제가 이루어질 때마다 실제 용량이 줄어드는 것을 알 수 있다.

공간이 2개나 비어 있는데 6이 큐에 못 들어간다. 이것은 메모리를 효율적으로 사용하지 못한 큐의 예이며,

언젠가 큐의 용량이 0으로 되어버릴 것이다.

 

이것을 해결하는 처리하는 방식이 2가지가 있는데, 그 방식에 따라 각각 선형큐(Liner Queue), 순환큐(Circular Queue)라고 한다.

 

선형큐(Liner Queue)는 삭제가 이루어질 때 마다 큐의 원소들를 각각 왼쪽으로 옮기는 방식이다.

이 방식으로 삽입,삭제가 무수히 이행되도 실제용량은 5로 고정되지만.

한번 삭제가 이루어 질 때마다 모든 배열의 원소를 옮기는 것이므로 너무 비효율적이다. 최악의 자료구조.

 

순환큐(Circular Queue)는 원소들을 옮기지 않고 반대로 전단과 후단의 유연하게 위치를 옮기는 방식이다. 

 후단이 배열의 맨 끝에 있을 때 6이 삽입(Enqueu)가 되면 배열의 첫부분으로 6을 삽입하는 하는 것이다. 

간단히 말하면 순환링크드리스트처럼 배열의 끝과 시작의 구분이 없어지는 것이다.

따라서 순환큐는 다시 이렇게 그려질 수 있다. 

이 방식은 삽입,삭제가 빠르고, 실제용량이 5로 고정되지만, 함수구현은 약간 까다롭다.

 

두번째로 비어있음(Empty)과 가득참(Full)을 어떻게 구별할 것인가이다.

먼저 비어있는 큐에 3을 삽입해보자.

 이 경우 큐가 비어있는 상태와 1개의 데이터가 있는 상태를 구별 할 수가 없다.(전단 = 후단)

이런 문제를 해결하기 위해 후단을 마지막 데이터의 다음 공간을 가리키게 한다.

이렇게 하면 전단과 후단이 같을 때(전단 = 후단)이 같을 때 비어있는(Empty) 상태라는 것을 알 수 있다.

그런데 이것 말고도 문제가 하나 더 있다.

바로 가득차있는 상태(Full)도 전단과 후단이 같아서

이번에는 공백상태(Empty), 가득차 있는 상태(Full)이 구별 하지 못한다.(전단 = 후단)

이 문제를 해결하기 위해서는 공백과 가득참의 상태를 구별하기 위해 후단을 위한 더미 공간을 하나를 사용한다.

큐의 용량(Capacity)이 4일 경우에 하나 더 추가해 5개의 공간을 사용하는 것이다. 

이런 식으로 공백(empty)일 때는 전단과 후단이 같다는 것을 이용하고(전단 = 후단)

가득참(full)일 때는 후단 다음이 전단이라는 사실을 이용한다.(후단->NextNode == 전단)

 

순환큐(Circular Queue)의 내용을 정리하면 다음과 같다.

1. 큐를 유연있게 사용하기 위해 배열의 시작과 끝이 경계선을 모호하게 만든다.

2. 공백상태와 1개의 데이터가 있는 상태를 구별하기 위해 후단의 위치를 마지막 데이터 다음 공간으로 한다.

3. 공백상태와 가득참상태를 구별하기 위해 실제 사용할 공간(Capacity)보다 더미노드를 위한 한개 더 선언한다.  

 

그럼 이제 배열로 구현한 순환큐(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_CreatQueue(CircularQueue** Queue, int Capacity){ (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue); (*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1)); //dummy node를 위해 //초기화 (*Queue)->Capacity = Capacity; (*Queue)->Front = 0; (*Queue)->Rear = 0; }

 

void CQ_DestroyQueue(CircularQueue** Queue){ free(Queue->Nodes); free(Queue); }

 

void CQ_Enqueue(CircularQueue* Queue, ElementType Data){ int Position = 0; if(Queue->Rear == Queue->Capacity){ //Rear가 array end Position = Queue->Rear; Queue->Rear = 0; } else{ Position = Queue->Rear++; } Queue->Nodes[Position].Data = Data; }

이 함수는 큐가 가득 찼는지 검사를 하지 않는다.( 전단 == 후단 +1 )

따라서 사용할 때 먼저 가득 찼는지 확인한다.

 

Element CQ_Dequeue(CircularQueue* Queue){ int Position = Queue->Front; if(Queue->Front == Queue->Capacity){ //Front가 array end Queue->Front = 0; } else Queue->Front++; return Queue->Nodes[Position].Data; }

이 함수는 큐가 비어 있는지 검사를 하지 않는다.( 전단 == 후단 )

따라서 사용할 때 먼저 비어 있는지 확인한다.

 

int CQ_IsEmpty(Circular* Queue){ return (Queue->Front == Qeueu-> Rear); }

큐가 비어 있다면 ===> true(정수값 1)

큐가 비어 있지 않다면 ===> false(정수값 0)

 포화상태는 2가지 경우가 있다.

전단 < 후단 일 경우 더미 노드로 인해 (후단 - 전단 == Capacity)가 참인 것을 확인하면 된다. 

 후단 < 전단일 경우 단순히 (후단 + 1 == 전단)가 참인 것을 확인 하면 된다.

int CQ_IsFull(Circular* Queue){ if(Queue->Front < Queue->Rear) //case 1 return (Queue->Rear - Queue->Front) == Queue->Capacity else //case 2 return (Queue->Rear +1) = Queue->Front }

 개수를 셀 때 2가지 경우가 있다.

전단 < 후단 일 경우에 더미노드로 인해 개수는 (후단 - 전단)

후단 < 전단일 경우 더미노드로 인해 개수는 (후단 + (Capacity-전단) +1)

int CQ_GetSize(CircularQueue* Queue){ if(Queue->Front <= Queue -> Rear) //case 1 return (Queue->Rear - Queue->Front); else //case 2 return Queue->Rear + (Queue->Capacity - Queue->Front) +1 }