[C/C++]큐 구조 - 선형큐,원형큐

스택과 더불어 자료구조하면 떠오르는 것인 큐를 구현해볼겁니다.

큐는 선입선출의 구조를 가집니다. 스택이 후입선출이었던 것과 차이점이죠. 먼저 들어온게 먼저 빠지는 어떻게 보면 실생활에서 자연스러운 구조입니다.

▶선형큐

#include <stdio.h>

#define MAX_QUEUE_SIZE 5

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

큐 구조체입니다. 큐는 스택이 인덱스로 top만 가졌던 것과는 다르게 front와 rear를 가집니다.

front는 dequeue, 스택으로 말하자면 pop이 일어날 때 움직이는 인덱스고 rear는 enqueue, push가 일어날 때 움직이는 인덱스 입니다.

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

스택과 마찬가지로 -1로 초기화 해줍니다.

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

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

is_full, is_empty 검사 입니다. full의 경우에는 rear에 집중하면 되고, empty의 경우에는 rear == front를 보면 됩니다.

선형 큐의 경우 rear==front의 경우가 공백상태일 때가 유일하기 때문입니다.

void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		error("큐가 포화상태입니다.\n");
		return 0;
	}
	q->data[++(q->rear)] = item;
}

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

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

enqueue 때는 rear를 먼저 하나 올리고, 그 자리에 원소를 넣습니다. 처음이 -1이기 때문에 자연스러운 겁니다. dequeue는 요소를 front를 하나 올려 빼서 반환합니다.

front만 움직이면 끝납니다. 선형큐에서 입력은 rear, 출력은 front임을 기억하면 됩니다.

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

int main() {
	element item = 0;
	QueueType 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);

	return 0;
}

main은 별 볼일 없고, print함수 돌아가는 원리만 살펴보겠습니다.

if(i<=q->front || i> q->rear)의 의미는 값이 없는 queue 의 나머지 공간입니다. 선형 큐에서 rear의 뒷공간, front의 앞공간이기 때문이죠. 그리고 else로 값 놓을 공간을 만듭니다.

front가 rear될 때 까지 했기 때문에 저런 결과가 나옵니다.

▶원형큐

선형큐는 front, rear값이 증가만 하기 때문에 언젠가는 공간의 끝에 도달하게 된다는 한계가 있습니다. 그래서 큐의 빈공간을 계속 쓰려면 주기적으로 원소들을 당겨주는 작업이 필요한데 그렇게 되면 시간도 많이 걸리고 코드도 복잡해집니다.

그 단점을 보완하기 위한 구조가 원형큐입니다.

원형큐는 나머지연산을 이용합니다. 공간의 끝에 도달하면 rear+1%x로 해서 공간의 처음(0)으로 보내는 거죠. 그 대신 초기값이 0으로 바뀌는 점을 기억해두세요. front는 항상 첫번째 요소 하나 앞을, rear는 마지막 요소를 가리킵니다.

#include <stdio.h>

#define MAX_QUEUE_SIZE 5

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

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

여기까지는 동일합니다.

void init_queue(QueueType* q) {
	q->rear = q->front = 0;
}
int is_full(QueueType* q) {
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

int is_empty(QueueType* q) {
	return (q->rear == q->front);
}

변화가 생긴게 보이시나요?? 우선 초기화 할 때 0으로 초기화합니다. full검사는 rear+1%MAX값이 front와 같으면 참값을 반환하고, empty는 rear==front일때 참값을 반환합니다.

이것으로 공백상태가 아닌 원형큐의 front,rear는 항상 포화상태일 때 한칸 차이 난다는 것을 알 수 있습니다.

front는 첫번째 값 하나 앞을 가리키고, rear는 마지막 값을 가리키기 때문이죠. 공백상태가 아닌데 front == rear라면 요소개수를 저장하고 있는 변수가 있어야합니다. 이때 full은 요소개수가 MAX값과 같을 때가 되겠군요.

void enqueue(QueueType* q, element item) {
	if (is_full(q)) error("큐가 포화상태입니다.");

	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element dequeue(QueueType* q) {
	if (is_empty(q)) error("큐가 공백상태입니다.");

	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

enqueue의 경우 rear값을 나머지연산을 통해 순환시킵니다. ++rear에서 벗어나 나머지연산의 여부를 확인해야하는 게 원형 큐에서 달라진 점입니다.

dequeue의 경우도 front를 나머지연산을 통해 순환시킵니다. ++front와 동일하다고 생각하시면 될 것 같아요.

void queue_print(QueueType* q) {
	printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % (MAX_QUEUE_SIZE);
			printf("%d | ", q->data[i]);
			if (i == q->rear) break;
		} while (i != q->front);
	}
	printf("\n");
}

출력함수는 front를 움직입니다. dequeue의 경우에만 앞에 걸 자르고 시작하겠죠(++front의 의미입니다.)

int main(){
	QueueType q;
	int element;

	init_queue(&q);
	while (!is_full(&q)) {
		printf("정수를 입력하세요: ");
		scanf_s("%d", &element);
		enqueue(&q, element);
		queue_print(&q);
	}

	while (!is_empty(&q)) {
		element = dequeue(&q);
		printf("꺼낸 정수: %d\n", element);
		queue_print(&q);
	}
	gets();
	return 0;
}

main함수는 이렇게 됩니다. 출력은 아래와 같구요.