[자료구조] 큐 (Queue)

큐란?

Queue라는 것은 뭘까요? 사전적 의미부터 살펴봅시다.

큐는 줄을 서서 기다리다 라는 의미를 가지고 있습니다. 사람이 줄을 서서 기다리는 모습을 상상할 수 있겠네요. 컴퓨터에서는 데이터가 줄을 이루는 자료 구조라고 생각하면 될 것 같습니다.

 

우리가 맛집을 찾아갔다고 상상해봅시다. 이 가게는 밥 먹을 시간이 되면 항상 사람이 붐비어 대기줄을 이룹니다. 오늘은 늦게 도착해서 앞에 대기줄이 길게 이루어져있네요. 밥을 먹기 위해 가게에 들어가려면 이 상황에서 어떻게 해야할까요? 앞에 있는 사람이 모두 들어가야 내가 들어갈 수 있겠죠. 그래야 비로소 제 차례가 와 맛집에 들어가 식사를 할 수 있을겁니다.

 

큐도 마찬가지입니다. 특정 데이터를 꺼내기 위해서는 앞에 있는 데이터를 모두 꺼내야 합니다. 이러한 특징을 바로 선입선출(FIFO; First In First Out) 이라고 합니다.

 

큐 ADT

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 자료 구조입니다. 스택과 비슷하지만 명확하게 다른 점이 하나 있습니다. 스택은 삽입과 삭제가 한 곳에서 이루어지지만, 큐는 삽입과 삭제가 다른 곳에서 이루어집니다. 삽입은 큐의 뒷쪽에서, 삭제는 앞쪽에서 이루어집니다.

create(max_size) ::= 크기가 size인 큐 생성
init(q) ::= 큐 초기화
is_full(q) ::= if(큐(q)의 원소 수 == size) return true; else return false;
is_empty(q) ::= if(q의 원소 수 == 0) return true; else return false;
enqueue(q, item) ::= if(is_full(q)) return FULL_ERROR; else q 맨 뒤에 item 추가
dequeue(q) ::= if(is_empty(q)) return EMPTY_ERROR; else q 맨 앞에 있는 item 제거 및 반환
peek(s) ::= if(is_empty(q)) return EMPTY_ERROR; else q 맨 앞 item 반환

 

선형 큐 (Linear Queue)

추상 자료형을 바탕으로 큐를 구현해봅시다.

 

큐 구조체

구조체를 이용해 큐의 구조를 지정해주면 됩니다.

typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
} Queue;

구조체 안에 front와 rear 변수가 선언되어 있습니다. front는 첫 번째 원소를 가리키고 rear는 마지막 원소를 가리킵니다. 스택에서는 하나만 있어도 되었지만 큐에서는 그렇게 하면 관리가 되지 않기 때문에 각각 변수를 선언해줍니다.

 

is_empty(q)

큐가 비어있는지 어떻게 확인할 수 있을까요? 원소가 없음을 알아야 하는데, 그 순간은 front와 rear이 같은 곳을 가리키고 있을 때입니다.

int is_empty(Queue *q) {
	if (q->front == q->rear) {
		return 1;
	} else {
		return 0;
	}
}

 

is_full(q)

큐가 꽉 차있는 상황인지 어떻게 확인할 수 있을까요? 꽉 찼다는 것은 가장 끝에 있는 원소가 마지막까지 도달했음을 의미합니다.

int is_full(Queue *q) {
	if (q->rear == MAX_QUEUE_SIZE - 1) {
		return 1;
	} else {
		return 0;
	}
}

 

enqueue(q, item)

큐에 원소를 삽입하는 함수입니다. 큐는 뒤에서부터 원소가 들어가는 형태이므로 rear이 가리키고 있는 인덱스에 넣어주면 됩니다.

void enqueue(Queue *q, int item) {
	if (is_full(q)) {
		fprintf(stderr, "큐가 꽉 차있습니다.");
		return;
	}
	q->data[++(q->rear)] = item; // rear 인덱스의 data 변수에 item으로 초기화 한 후 rear + 1
}

 

dequeue(q)

큐에 원소를 제거하는 함수입니다. 큐는 앞으로 원소가 나오는 형태이므로 front가 가리키고 있는 인덱스를 빼주면 됩니다.

int dequeue(Queue *q) {
	if(is_empty(q)) {
		fprintf(stderr, "큐가 비어있습니다.");
		return -1;
	}
	int item = q->data[++(q->front)]; // front 인덱스의 data 변수를 item 변수에 초기화 한 후 front + 1
	return item; // 제거된 숫자를 return
}

 

peek(q)

큐의 가장 앞에 있는 원소를 반환하는 함수입니다. front가 가리키고 있는 값을 반환해주면 됩니다.

int peek(Queue *q) {
	if(is_empty(q)) {
		fprintf(stderr, "큐가 비어있습니다.");
		return -1;
	}
	int item = q->data[q->front];
	return item;
}

 

전체적인 코드는 아래와 같습니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct {
	int front;
	int rear;
	element data[MAX_QUEUE_SIZE];
} Queue;

void error(char *message) {
	fprintf(stderr, "%s\\n", message);
	exit(1);
}

void init_queue(Queue *q) {
	q->rear = -1;
	q->front = -1;
}

void queue_print(Queue *q) {
	for(int i = 0; i < MAX_QUEUE_SIZE; i++) {
		if(i <= q->front || i > q->rear) {
			printf(" | ");
		} else {
			printf("%d | ", q->data[i]);
		}
	}
	printf("\\n");
}

int is_full(Queue *q) {
	if (q->rear == MAX_QUEUE_SIZE - 1) {
		return 1;
	} else {
		return 0;
	}
}

int is_empty(Queue *q) {
	if (q->front == q->rear) {
		return 1;
	} else {
		return 0;
	}
}

void enqueue(Queue *q, int item) {
	if (is_full(q)) {
		error("큐가 꽉 차있습니다.");
		return;
	}
	q->data[++(q->rear)] = item;
}

int dequeue(Queue *q) {
	if(is_empty(q)) {
		error("큐가 비어있습니다.");
		return;
	}
	int item = q->data[++(q->front)];
	return item;
}

int peek(Queue *q) {
	if(is_empty(q)) {
		fprintf(stderr, "큐가 비어있습니다.");
		return -1;
	}
	int item = q->data[q->front];
	return item;
}

int main() {
	int item = 0;
	Queue q;

	init_queue(&q);

	enqueue(&q, 10); queue_print(&q);
	enqueue(&q, 20); queue_print(&q);
	enqueue(&q, 30); queue_print(&q);

	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
}

출력 결과.

선형 큐의 단점

이렇게 선형 큐를 구현하게 되면 단점이 생깁니다. 삽입을 해도 기존의 수가 앞으로 당겨지지 않으니 rear의 인덱스 값이 끝에 도달하면 더 이상 큐에 삽입 연산을 진행할 수 없다는 것입니다. 그래서 다음에 다룰 원형 큐에서는 이를 보완해 인덱스가 자동적으로 변환되도록 구현해볼 것입니다.