[CS과목/자료구조] 05 큐

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

5.1 큐 추상 데이터 타입

 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 다시 말해, 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 이러한 특성을 선입선출(FIFO: First-In First-Out)이라고 한다. 큐에서 삽입이 일어나는 곳을 후단(rear)라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다. 큐에서 가장 중요한 연산은 삽입과 삭제 연산인 enqueue와 dequeue이다. enqueue 연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소를 추가한다. dequeue 연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환한다. 큐의 응용으로 예를 달면 운영 체제에는 인쇄 작업 큐가 존재한다. 프린터는 속도가 늦고 상대적으로 컴퓨터의 CPU는 속도가 빠르게 때문에 CPU는 빠른 속도로 인쇄 데이터를 만단 다음, 인쇄 작업 큐에 저장하고 다른 작업으로 넘어간다.

 

5.2 선형큐

 큐는 규현하는 방법이 여러가지가 있다. 여기서는 가장 간단한 방법, 즉 1차원 배열을 쓰는 방법을 먼저 살펴보자. front와 rear의 초기값은 -1이다. 데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장된다. 삭제할 때도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다.

#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];
} QueueType;

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

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

void queue_print(QueueType* 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(QueueType* q)
{
	if (q->rear == MAX_QUEUE_SIZE - 1)
		return 1;
	else
		return 0;
}

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

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

int dequeue(QueueType* q)
{
	if (is_empty(q)) {
		error("큐가 공백상태입니다.");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

int main(void)
{
	int 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;
}

 

 선형큐는 이해하기 쉽지만 문제점이 있다. front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지를 못한다는 점이다. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 한다.

 

5.3 원형큐

 선형큐의 문제를 해결하기 위해 배열을 원형으로 생각하면 된다. front와 rear의 값이 배열의 끝인 (MAX_ QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록하여 처음과 끝이 연결되어 있다고 생각하는 것이다. front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타낸다. 원형큐에서는 하나의 자리는 항상 비워둔다. 왜냐하면 포화 상태와 공백 상태를 구별하기 위해서이다. 만약 front==rear이면 공백 상태가 되고 front가 rear보다 하나 앞에 있으면 포화 상태가 된다. 원형큐의 구현에 있어서 중요한 것은 front와 rear를 원형으로 회전시켜야 한다는 것이다. 이는 나며지 연산자 %를 이용하여 쉽게 구현할 수 있다.

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

int dequeue(QueueType* q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다.");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

int main(void)
{
	QueueType q;
	int i = 0, element;

	init_queue(&q);
	printf("--데이터 추가 단계--\n");
	while (!is_full(&q))
	{
		enqueue(&q, i*10); queue_print(&q);
		i++;
	}
	printf("큐는 포화상태입니다.\n\n");

	printf("--데이터 삭제 단계--\n");
	while (!is_empty(&q))
	{
		element = dequeue(&q); queue_print(&q);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}

 

5.5 덱이란?

 덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 덱은 스택과 큐의 연산들을 모두 가지고 있다. 예를 들면 add_front와 delete_front 연산은 스택의 push와 pop 연산과 동일하다. 또한 add_rear 연산과 delete_front 연산은 큐의 enqueue와 dequeue 연산과 같다. 덱에서 delete_rear와 add_front에서는 원형큐에서와 다르게 반대 방향의 회전이 필요하다. front나 rear를 감소시켜야 하는데, 만약 음수가 되면 MAX_QUEUE_SIZE를 더해주어야 한다.

void add_rear(DequeType* q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다.");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element delete_front(DequeType* q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다.");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

// deque에서 추가된 2가지 기능: add_front, delete_rear
void add_front(DequeType* q, element val)
{
	if (is_full(q))
		error("큐가 포화상태입니다.");
	q->data[q->front] = val;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

element delete_rear(DequeType* q)
{
	int prev = q->rear;
	if (is_empty(q))
		error("큐가 공백상태입니다.");
	q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return q->data[prev];
}