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

큐는 스택과 반대의 특성인 선입선출(First In, First Out)의 특성을 가지고 있습니다. 선입선출의 특성은 앞에서 작업의 처리가 끝나면 다음 작업이 실행될 수 있게 하는 완충장치로써 많이 사용됩니다.

가령 쇼핑몰이나, 특정한 사이트에서 카카오톡 채팅상담을 보신적이 있으실 겁니다. 상담사는 1명이지만, 상담을 받으려는 사람은 많기 때문에 큐를 사용하여 한 사람의 상담이 끝날 때까지 다른 사람은 대기하도록 하는 것이 큐의 사용입니다.

 

스택에서는 노드의 삽입과 제거가 최상위 노드에서만 이루어졌지만, 큐는 제거는 제일 전단에서 삽입은 후단에서 이루어집니다.

큐

 

큐는 크게 배열로 만들어지는 순환 큐(Circular Queue)와 링크드 큐(LinkedQueue)가 있습니다.

하나하나씩 알아가보도록 하겠습니다.

 

순환 큐(Circular Queue)

---

배열로 큐를 구현할때는 문제점이 있습니다.

전단과 후단의 위치를 인덱스 번호로써 나타내는데 배열은 크기가 고정되어 있기 때문에 전단의 위치가 배열의 마지막에 도달했을 때 더 이상 데이터를 담을 수 없다는 것입니다.

 

그 해답이 순환입니다. 

 

후단의 위치가 배열의 끝에 도달했을 때 후단의 위치를 배열의 첫 번째 인덱스로 옮기면서 용량의 한계를 해결할 수 있습니다. 하지만 이 경우에는 순환 큐가 가득 차 있는 상태와 비어있는 상태를 구별할 수 없습니다. 두 상태에서는 전단과 후단의 위치가 같기 때문이죠 이때 배열을 생성할 때 용량을 실제보다 1만큼 크게 만들어 전단과 후단 사이를 하나 비움으로써 해결할 수 있습니다.

 

순환 큐는 아래와 같은 데이터 구조를 가지고 있습니다.

typedef struct tagNode {
	int Data;
}Node;

typedef struct  tagCircularQueue
{
	int Capacity; //큐의 용량 실제용량보다 하나 작다
	int Front; //전단의 위치(제거되는 노드가 위치해있는 곳)
	int Rear; //후단의 위치(들어오는 입구) 실제 후단보다 1더 큰 값
	Node* Nodes; //노드의 배열
}CircularQueue;

 

순환 큐(Circular Queue)의 생성

---

void CQ_CreateQueue(CircularQueue** Queue, int Capacity) {
	(*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
	(*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1)); //입력된 Capecity 보다 1크게 노드를 자유 저장소에 생성

	(*Queue)->Front = 0;
	(*Queue)->Rear = 0;
	(*Queue)->Capacity = Capacity;
}

순환 큐 안에 있는 노드의 배열을 자유 저장소에 생성할 때 입력된 매개변수 Capacity 보다 1만큼 크게하여 생성합니다.

 

 

순환 큐(Circular Queue)의 삽입과 제거

---

삽입은 후단의 위체에 의해서 들어가게 됩니다. 그러므로 삽입 연산의 후단의 위치를 잘 다루는 것이 핵심이라고 할 수 있죠.

void CQ_Enqueue(CircularQueue* Queue, int Data) {
	int Position = 0;
	
	if (Queue->Rear == Queue->Capacity) { //후단이 용량의 끝이라면(실제용량은 +1이기 때문에 전단과 후단사이가 하나 비어있음)
		Position = Queue->Rear; // Position은 후단이고
		Queue->Rear = 0; //후단을 0으로 보냄
	}
	else { //용량의 끝이 아니라면
		Position = Queue->Rear++; //Postion은 후단이고 후단은 다음 배열로 보냄
	}

	Queue->Nodes[Position].Data = Data; // Position자리에 노드 삽입

}

 

순환 큐에서 제거 연산은 전단을 잘 관리해 주는 것이 중요합니다. 조금만 생각해봐도 전단에서는 제거 연산이 일어나고 후단에서는 삽입 연산이 일어나기 때문이죠.

 

제거 연산에서는 삭제한 큐의 인덱스가 용량과 같을 때 배열의 끝에 도달한 것이므로 전단의 인덱스를 0으로 초기화하는 것이 기억해주면 됩니다.

 

위의 그림에서 배열의 전단인 6을 제거했을 때, 전단의 위치가 배열의 끝이므로

제거 후에 전단의 위치를 0으로 초기화해줍니다.

int CQ_Dequeue(CircularQueue* Queue) {
	int Position = Queue->Front; // 전단의 위치를 Position에 저장

	if (Queue->Front == Queue->Capacity) { 전단의 위치가 용량과 같으면 배열의 끝이므로
		Queue->Front = 0; 전단의 위치를 0으로
	}
	else { 아니면 전단의 위치 1더하기
		Queue->Front++;
	}

	return Queue->Nodes[Position].Data; // 삭제한 인덱스 번호 리턴
}

 

공백, 포화 상태 확인

---

순환 큐에서 공백 상태인지 확인하는 방법은 전단의 위치와 후단의 위치가 같은지 보면 됩니다.

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

 

포화 상태인지 확인할 때는 두가지로 나누어집니다.

전단의 위치가 후단보다 앞에 위치하면 후단과 전단의 차가 큐의 용량과 동일한지 보고 반대인 경우에는 전단에 1의 더한 값이 후단의 값과 동일한지 확인합니다.

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

 

큐의 구현은 배열과 링크드 리스트로 가능합니다.

배열과 링크드 리스트의 차이점은 링크드 리스트에는 배열처럼 용량의 제한이 없기 때문에 가득 차있는지 확인할 필요도 없고 구현도 배열보다는 간단합니다. 하지만 성능은 배열이 더 빠르기 때문에 큐의 크기가 예측 가능하고 고성능이 필요할 때는 순환 큐를 사용하는 것이 더 좋습니다.

 

다음 시간에는 링크드 큐에 대해 알아보도록 하겠습니다.