[알고리즘] 큐(queue)

큐 (queue)

큐 자료 구조는 스택과 유사하게 일종의 리스트라고 할 수 있다. 단, 큐에서 데이터의 삽입은 한 쪽 끝에서, 삭제는 반대쪽 끝에서만 일어난다. (FIFO, First-in First-out) 이때 삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front라고 한다.

• 큐의 주요 연산

연산	설명
insert, enqueue, offer, push	큐의 rear에 새로운 원소를 삽입한다.
remove, dequeue, poll, pop	큐의 front에 있는 원소를 삭제하고 반환한다.
peek, element, front	큐의 front에 있는 원소를 삭제하지 않고 반환한다.
is_empty	큐가 비어있는지 검사한다.

헤더 파일 queueADT.h에 함수들을 따로 선언해놓고 c파일에서 인클루드하면 보다 편리하게 큐 자료 구조를 사용할 수 있다.

• queueADT.h

#ifndef QUEUEADT_H
#define QUEUEADT_H

#include <stdbool.h>

typedef int Item;
typedef struct queue_type* Queue;

Queue create();
void destroy(Queue q);
void make_empty(Queue q);
bool is_empty(Queue q);
void enqueue(Queue q, Item i);
Item dequeue(Queue q);
Item peek(Queue q);
int get_size(Queue q);

#endif

1. 배열을 이용한 큐 구현

#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"

#define INIT_CAPACITY 100

struct queue_type {
	Item* contents; // 배열
	int front;
	int rear;
	int size; // 저장된 데이터의 개수
	int capacity; // 배열 contents의 크기
};

void terminate(const char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

int get_size(Queue q) {
	return q->size;
}

Queue create()
{
	Queue q = (Queue)malloc(sizeof(struct queue_type));
	if (q == NULL)
		terminate("Error in create: queue could not be created.");
	q->contents = (Item*)malloc(INIT_CAPACITY * sizeof(Item));
	if (q->contents == NULL) {
		free(q);
		terminate("Error in create: queue could not be created.");
	}
	q->front = 0;
	q->rear = -1;
	q->size = 0;
	q->capacity = INIT_CAPACITY;
	return q;
}

void destroy(Queue q)
{
	free(q->contents);
	free(q);
}

void make_empty(Queue q)
{
	q->front = 0;
	q->rear = -1;
	q->size = 0;
}

bool is_empty(Queue q)
{
	return q->front == NULL;
}

bool is_full(Queue q)
{
	return q->size == q->capacity;
}

void enqueue(Queue q, Item i)
{
	if (is_full(q))
		reallocate(q);
	// rear가 배열의 마지막일 경우 배열의 0으로 되돌려준다.
	q->rear = (q->rear + 1) % q->capacity;
	q->contents[q->rear] = i;
	q->size++;
}

Item dequeue(Queue q)
{
	if (is_empty(q))
		terminate("Error in dequeue: queu is empty.");
	Item result = q->contents[q->front];
	q->front = (q->front + 1) % q->capacity;
	q->size--;
	return result;
}

Item peek(Queue q)
{
	if (is_empty(q))
		terminate("Error in dequeue: queue is empty.");
	return q->contents[q->front];
}

void reallocate(Queue q)
{
	Item* tmp = (Item*)malloc(2 * q->capacity * sizeof(Item));
	if (tmp == NULL) {
		terminate("Error in create: queue could not be expanded.");
	}
	// 배열 큐는 원 형태이므로(환형배열) 배열 값에 상관없이 front부터 rear를 복사한다.
	int j = q->front;
	for (int i = 0; i < q->size; i++) {
		tmp[i] = q->contents[j];
		j = (j + 1) % q->capacity;
	}
	free(q->contents);

	q->front = 0;
	q->rear = q->size - 1;
	q->contents = tmp;
	q->capacity *= 2;
}

위 코드에선 구조체를 통해 원형 큐(Circular Queue)를 배열로 구현하고 있다.

2. 연결리스트를 이용한 큐 구현

• queueADT.c

#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"

struct node {
	Item data;
	struct node* next;
};

struct queue_type {
	struct node* front;
	struct node* rear;
	int size;
};

void terminate(const char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

int get_size(Queue q) {
	return q->size;
}

Queue create()
{
	Queue q = (Queue)malloc(sizeof(struct queue_type));
	if (q == NULL)
		terminate("Error in create: queue could not be created.");
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
	return q;
}

void destroy(Queue q)
{
	make_empty(q);
	free(q);
}

void make_empty(Queue q)
{
	while (!is_empty(q))
		dequeue(q);
	q->size;
}

bool is_empty(Queue q)
{
	return q->front == NULL;
}

void enqueue(Queue q, Item i)
{
	struct node* new_node = malloc(sizeof(struct node));
	if (new_node == NULL)
		terminate("Error in push: queue is full.");

	// new_node를 연결리스트의 맨 뒤(rear)에 삽입한다.
	new_node->data = i;
	new_node->next = NULL;
	// queue가 empty list인 경우
	if (q->front == NULL) {
		q->front = new_node;
		q->rear = new_node;
	}
	else {
		q->rear->next = new_node;
		q->rear = new_node;
	}
	q->size++;
}

Item dequeue(Queue q)
{
	struct node* old_front;
	Item i;

	if (is_empty(q))
		terminate("Error in dequeue: queue is empty.");

	// 첫번째 노드(front)를 삭제하고 삭제된 노드의 데이터를 return
	old_front = q->front;
	i = old_front->data;
	q->front = old_front->next;
	// 유일한 노드를 삭제하고 empty가 된 경우
	if (q->front == NULL)
		q->rear = NULL;
	free(old_front);
	q->size--;
	return i;
}

Item peek(Queue q)
{
	if (is_empty(q))
		terminate("Error in dequeue: queue is empty.");
	return q->front->data;
}

참고자료
큐의 개념과 구현 / https://youtu.be/_aU2e70gYlo