큐 (Queue)

먼저 들어가고 먼저 나오는 FIFO(First In, First Out), 또는 선입선출 자료구조를 큐라고 한다.

큐의 주요 연산은 삽입과 제거이다.

<그림 1> 큐의 삽입 연산 (Enqueue)

<그림 2> 큐의 제거 연산 (Dequeue)

큐는 두 가지 방법으로 구현이 가능하다. 하나는 순환 큐 (Circular Queue), 그리고 연결 큐 (Linked Queue) 이다.

1. 순환 큐 (Circular Queue)

말 그대로 순환하는 큐이다. 배열의 크기를 미리 지정한 후에 그 크기에 맞춰 순환하는 큐이다.

그림을 보면 쉽게 이해가 갈 것이다.

배열의 크기는 6이고, 크기 6에 따라 순환하면서 데이터 값을 삽입하고 있는 모습이다. 개념 상으로는 왼쪽그림으로 생각하면

될 것이고 실제로는 오른쪽 그림과 같이 동작을 한다.

위의 개념을 토대로 구현하기에 앞서 순환 큐의 문제점에 대해서 보도록 하겠다.

위와 같은 상황에서 비어있는지, 가득 차 있는지 어떻게 구분할 것인가?

해결 방법은 간단하다. 

위의 그림과 같이 실제의 크기보다 1만큼 더 크게 만들어서 전단과 후단 사이를 비우는 것이다.

전단과 후단이 같은 곳을 가리킬 때는 비어있다는 것이고, 전단과 후단 사이의 간격이 1이면 가득 차있다는 뜻이 된다.

지금부터 순환 큐를 구현해보겠다.

//큐 구조체
typedef struct tagNode {
	int Data;
} Node;


typedef struct tagQueue {
	int Capacity;	// 용량
	int Front;		// 전단의 인덱스
	int Rear;		// 후단의 인덱스
	Node* Nodes;	// 노드 배열
} Queue;


//순환 큐 생성
void createQueue(Queue** queue, int Capacity) {
	//큐 생성
	(*queue) = (Queue*)malloc(sizeof(Queue));
	//노드 생성
	(*queue)->Nodes = (Node*)malloc(sizeof(Capacity+1));
	//큐 정보 초기화
	(*queue)->Capacity = Capacity;
	(*queue)->Front = 0;
	(*queue)->Rear = 0;
}

//순환 큐 반환
void destroyQueue(Queue* queue) {
	free(queue->Nodes);
	free(queue);
}

//삽입(Enqueue) 연산
void enQueue(Queue* queue, int data) {
	int Position = 0;
	if(queue->Rear == queue->Capacity) {
		Position = queue->Rear;
		queue->Rear = 0;
	} else {
		Position = queue->Rear++;
	}
	queue->Nodes[Position].Data = data;
}

//제거(Dequeue) 연산
int deQueue(Queue* queue) {
	int Position = queue->Front;

	if(queue->Front == queue->Capacity) {
		queue->Front = 0;
	} else {
		queue->Front++;
	}
	return queue->Nodes[Position].Data;
}

//공백 상태 확인
bool isEmpty(Queue* queue) {
	return (queue->Front == queue->Rear);
}

//포화 상태 확인
bool isFull(Queue* queue) {
	if(queue->Front < queue->Rear)
		return (queue->Rear - queue->Front) == queue->Capacity;
	else
		return (queue->Rear + 1) == queue->Front;
}

2. 연결 큐 (Linked Queue)

다음은 연결 큐이다. 

연결 큐는 용량에 제한을 받지 않는다. 그리고 개념적으로 그리고 구현할 때에 있어 순환 큐보다 쉽다는 장점이 있다.

하지만 단점도 존재한다. 속도 면에서는 순환 큐보다 느리다. 이유는 동적 할당이라는 비용이 더 들기 때문이다.

밑의 그림을 보면 연결 큐가 어떻게 동작하는 지 볼 수 있다.

그럼 연결 큐를 구현해보겠다.

// 연결 큐 구조체
typedef struct tagNode {
	int Data;
	struct tagNode* NextNode;
} Node;

typedef struct tagQueue {
	Node* Front;
	Node* Rear;
	int Count;
} Queue;

// 큐 생성
void createQueue(Queue** queue) {
	(*queue) = (Queue*)malloc(sizeof(Queue));
	
	//큐 초기화
	(*queue)->Count = 0;
	(*queue)->Front = NULL;
	(*queue)->Rear = NULL;
}

// 큐 반환
void destroyQueue(Queue* queue) {
	while(queue->Count) {
		Node* temp = deQueue(queue);
		free(temp);
	}
	free(queue);
}

//삽입(Enqueue) 연산
void enQueue(Queue* queue, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->Data = data;
	newNode->NextNode = NULL;

	if( queue->Front == NULL ) {
		queue->Front = newNode;
		queue->Rear = newNode;
		queue->Count++;
	} else {
		queue->Rear->NextNode = newNode;
		queue->Rear = newNode;
		queue->Count++;
	}
}

//제거(Dequeue) 연산
Node* deQueue(Queue* queue) {
	Node* Front = queue->Front;

	if( queue->Front->NextNode == NULL ) {
		queue->Front = NULL;
		queue->Rear = NULL;
	} else {
		queue->Front = queue->Front->NextNode;
	}
	queue->Count--;

	return Front;
}