큐(Queue)

큐란?

사진 출처 : https://ko.wikipedia.org/wiki/큐_(자료_구조)

• Queue : (무엇을 기다리는 사람 자동차 등의) 줄 (출처 : 네이버 영어사전)
• 선입선출(FIFO : First in First out)의 방식을 사용하는 자료구조
• 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

큐의 종류

• 선형 큐

배열로 큐를 구현하기 때문에 크기가 제한되어 있다.

연산을 반복한 뒤에 rear가 배열의 마지막까지 갔을 때 실제로는 앞에 공간이 남아있지만 삽입 연산을 실행했을 때 오버플로우가 발생한다.

사진 출처 : https://book.naver.com/bookdb/book_detail.nhn?bid=14566230

• 원형큐

위에서 설명한 선형 큐의 문제점(오버플로우가 발생)을 보완한 큐이다.

rear가 배열의 마지막까지 갔을 때 삽입 연산을 실행하면 모듈러 연산을 통해 맨 앞에 데이터를 삽입해 원형으로 연결하는 방식이다.

공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.

사진 출처 : https://book.naver.com/bookdb/book_detail.nhn?bid=14566230

큐의 연산

• enqueue(q, e) : 큐에 데이터를 추가
• dequeue(q) : 큐의 맨 앞에 있는 데이터를 반환하고 삭제
• is_full(q) : 큐 포화상태 검사
• is_empty(q) : 큐 공백상태 검사
• peek(q) : 큐의 맨 앞에 있는 데이터를 반환, 삭제X

큐 사용 예시

• BFS(깊이우선탐색) 알고리즘에 큐를 사용한다.

---

배열을 이용한 선형큐 구현

#define QUEUE_SIZE 100
int queue[QUEUE_SIZE];
int f = -1, r = -1;
int is_full() {
	if (r == QUEUE_SIZE - 1) return 1;
	else return 0;
}
int is_empty() {
	if (r == f) return 1;
	else return 0;
}
void enqueue(int x) {
	queue[++r] = x;
}
int dequeue() {
	if (is_empty()) return -1;
	else return queue[++f];
}
int peek() {
	if (!is_empty()) return queue[f + 1];
}

구조체를 이용한 원형큐 구현

공백상태: front == rear, 포화상태: front == (rear + 1) % QUEUE_SIZE

#define QUEUE_SIZE 100
typedef struct {
	int data[QUEUE_SIZE];
	int front, rear;
} QueueType;
void init_queue(QueueType* q) {
	q->front = q->rear = 0;
}
int is_full(QueueType* q) {
	return ((q->rear + 1) % QUEUE_SIZE == q->front);
}
int is_empty(QueueType* q) {
	return (q->front == q->rear);
}
void enqueue(QueueType* q, element item) {
	if (!is_full(q)) {
		q->rear = (q->rear + 1) % QUEUE_SIZE;
		q->data[q->rear] = item;
	}
}
int dequeue(QueueType* q) {
	if (!is_empty(q)) {
		q->front = (q->front + 1) % QUEUE_SIZE;
		return q->data[q->front];
	}
}

연결리스트를 이용한 링크드 큐 구현

연결리스트를 사용하기 때문에 배열을 사용한 선형 큐와 달리 오버플로우가 발생하지 않는다.

typedef struct Node {
	int data;
	struct Node* next;
} Node;
typedef struct Queue {
	Node* front;
	Node* rear;
	int count;
} Queue;
void init_queue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
int is_empty(Queue* queue) {
	return queue->count == 0;
}
void enqueue(Queue* queue, int data) {
	Node* now = (Node*)malloc(sizeof(Node));
	now->data = data;
	now->next = NULL;
	if (is_empty(queue)) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
int dequeue(Queue* queue) {
	if (queue->count == 0) {
		return -1;
	}
	Node* now = queue->front;
	int re = now->data;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int peek(Queue* queue) {
	if (is_empty(queue)) return -1;
	else return queue->front->data;
}