JArchive 프로그래밍 일기

큐

큐는 먼저 들어온 일부터 먼저 처리하는 자료구조 입니다. 

선입 선출, First In First Out (FIFO) 라고 합니다. 

큐의 기능 

큐의 가장 앞 요소를 전단, 마지막 요소를 후단이라고 합니다. 

(스택은 최상위 노드가 있는 입구에서만 삽입/제거가 수행됩니다. )

큐는 전단에서 Dequeue (제거) 되고, 후단에서만 Enqueue (삽입) 됩니다. 

순환 큐 

유의할 점은 큐가 비었는지 가득찼는지 구분을 위해 큐를 실제 용량보다 1 크게 만드는 것입니다. 

용량이 7인 큐를 만든다고 하면, 

구현할 때는 8인 큐를 만듭니다. 

비었을 때는 전단과 후단이 같은 곳을 가리킵니다 

큐가 꽉 찼을 때는 후단 바로 다음이 전단이 됩니다. 

이렇게 후단과 전단 사이에 공간을 두어 큐의 상태를 구분합니다. 

후단은 실제 데이터가 있는 칸의 바로 다음칸을 가리키고 있음을 유의해야 합니다.

후단 인덱스는 항상 빈 칸을 가리키고 있어야 합니다. 

순환 큐 구현

노드와 큐 구조체를 선언합니다.

typedef struct Node {
	int data;
};

typedef struct Cqueue {
	int capacity;
	int front;
	int rear;
	Node* nodeArray;
};

Cqueue구조체에서 nodeArray 포인터는 자유저장소에 존재하는 배열의 첫번째 칸을 가리킵니다. 

공백과 포화를 구분하기 위해 실제 capacity + 1하기 위한 '더미 노드'를 하나 둡니다.  

큐를 만들고 메모리 해제하는 함수 

void CreateCqueue(Cqueue** cqueue, int capacity) {

	(*cqueue) = (Cqueue*)malloc(sizeof(Cqueue));

	(*cqueue)->capacity = capacity;
	(*cqueue)->front = 0;
	(*cqueue)->rear = 0;
	(*cqueue)->nodeArray = (Node*)malloc(sizeof(Node) * (capacity + 1));

}

nodeArray 라는 이름의 배열은 사용자가 요구한 용량보다 1개 크게 만들어집니다. 더미 노드를 포함하기 때문입니다. 

void FreeCqueue(Cqueue* cqueue) {

	free(cqueue->nodeArray);
	free(cqueue);
}

삽입(Enqueue)

뒤에서 삽입하니까 rear를 관리합니다. 

rear는 항상 삽입'할' 타겟 인덱스를 가리키고 있습니다.

즉, 빈 공간을 가리키고 있다는 뜻입니다. 

capacity + 1인 인덱스는 공백/포화를 구분할 더미노드의 위치입니다. 

void Enqueue(Cqueue* cqueue, int data) {

	int position = 0;

	if (cqueue->capacity + 1 == cqueue->rear) {
		position = cqueue->rear;
		cqueue->rear = 0;
	}
	else {
		position = cqueue->rear++;
	}

	cqueue->nodeArray[position].data = data;
}

제거(Dequeue)

앞에서 제거하니까 front를 관리합니다. 

front와 capacity가 같은 상황은 전단이 배열 맨 끝에 와있다는 것입니다. 

노드를 하나 제거 하면, 인덱스를 0으로 돌려놔야 합니다. 

이 경우를 제외하면 front를 하나 감소시키면 됩니다.

int Dequeue(Cqueue* cqueue) {

	int position = cqueue->front;

	if (cqueue->front == cqueue->capacity ) {
		cqueue->front = 0;
	}else{
		cqueue->front++;
	}
	
	return cqueue->nodeArray[position].data;
}

큐의 공백과 포화 확인하기 

공백 : front 와 rear 가 같은 곳을 가리키고 있습니다. 

int IsEmpty(Cqueue* cqueue) {
	return 	(cqueue->front == cqueue->rear);
}

포화: rear의 바로 다음이 front 입니다. 또는 rear에서 front를 빼면 그 길이가 capacity가 됩니다. 

int IsFull(Cqueue* cqueue) {
	if (cqueue->front < cqueue->rear) {
		return (cqueue->rear - cqueue->front == cqueue->capacity);
	}
	else {
		return (cqueue->front == cqueue->rear + 1);
	}
}

메인함수 - 삽입/제거 해보기 

5개를 저장할 수 있는 배열을 만들고, 8번 삽입, 6번 제거해봤습니다. 

삽입 전에 포화인지 검사하고 포화이면 탈출합니다. 

제거 전에 비었는지 검사하고 비었으면 탈출합니다. 

int main(void) {

	int i = 0; 
	Cqueue* queue;

	// 5개를 저장할 수 있는 배열 
	CreateCqueue(&queue, 5);

	// 8번 삽입 
	for (int cnt = 1; cnt < 9; cnt++) {
		if (!IsFull(queue)) {
			printf("%d를 삽입.\n", cnt);
			Enqueue(queue, cnt);
		}
		else {
			printf("큐가 꽉 찼습니다.\n");
			break;
		}
	}

	// 6번 제거
	for (int cnt = 1; cnt < 7; cnt++) {
		if (!IsEmpty(queue)) {
			printf("%d 를 제거.\n", Dequeue(queue));
		}
		else {
			printf("큐가 비었습니다.\n");
			break;
		}
	}

	return 0;
}