[C언어][자료구조] 선형 큐(Linear Queue)

※ 이 글은 C언어 기준으로 작성하였습니다.

 

큐

---

저번 글에서 큐는 줄서기와 같다고 했습니다.

 

먼저 입력된 데이터가 먼저 출력되는 FIFO 구조를 가지고 있습니다.

 

큐가 스택과 구조적으로 다른 점은 스택은 삽입과 삭제가 같은 쪽(top)에서 일어나는 반면,

 

큐에서는 삽입(rear)과 삭제(front)가 다른 쪽에서 일어납니다.

 

데이터 삽입은 rear에서 일어나고 삭제는 front에서 일어납니다.

 

이번 글에서는 선형큐를 구현해보겠습니다.

 

code

---

#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)
{
	int i;
	for (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)) {
		fprintf(stderr, "Full!\n");
		exit(1);
	}
	q->data[++(q->rear)] = item;
}

int dequeue(Queue *q)
{
	if (is_empty(q)) {
		fprintf(stderr, "Empty!\n");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

int main(void)
{
	int item;
	Queue q;

	init_queue(&q);

	enqueue(&q, 43); queue_print(&q);
	enqueue(&q, 21); queue_print(&q);
	enqueue(&q, 77); queue_print(&q);

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

 

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

Queue 구조체입니다.

 

front와 rear 그리고 data배열로 이뤄져 있습니다.

 

하나의 큐만 있다면 구조체를 만들 필요가 없겠지만,

 

큐가 여러개 일 때, 각각 큐마다 front와 rear를 구분해줘야 하니

 

복잡해질 수 있습니다. 그러니 편하게 관리하기 위해 구조체를 만드는 것입니다.

 

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

큐를 초기화하는 함수입니다.

 

선형큐에서는 rear와 front를 -1로 초기화합니다.

 

void queue_print(Queue *q)
{
	int i;
	for (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;
}

스택에서도 봤던 is_full과 is_empty입니다.

 

is_empty의 조건이 front == rear인 것은 나중에 출력결과를 보시면 이해하기 쉽습니다.

 

void enqueue(Queue *q, int item)
{
	if (is_full(q)) {
		fprintf(stderr, "Full!\n");
		exit(1);
	}
	q->data[++(q->rear)] = item;
}

enqueue함수 입니다. 스택의 push와 같습니다.

 

rear의 값을 1증가시키고 data배열의 rear위치에 입력값 item을 넣습니다.

 

int dequeue(Queue *q)
{
	if (is_empty(q)) {
		fprintf(stderr, "Empty!\n");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

 dequeue함수 입니다. 스택의 pop과 같습니다.

 

front의 값을 1증가시키고 data배열의 front위치의 값을 item에 넣고, 출력합니다.

 

선형 큐의 단점

---

enqueue가 실시될 때마다 맨앞에서부터 차례대로 데이터가 삽입됩니다.

 

dequeue가 실시될 때마다 맨앞에서부터 차례대로 데이터가 삭제됩니다.

 

하지만 dequeue가 실시된다고 뒤에 있던 데이터들이 앞으로 땡겨지지 않습니다. 

 

그렇게 할 수는 있지만, 그러면 매번 재정렬을 해줘야 합니다.

 

그러면 코드도 복잡해지고 수행시간도 상당히 길어지게 됩니다.

 

여기서 선형 큐의 단점이 드러납니다.

 

95, 24, 15, 67 총 4개의 값을 더 입력했더니 2개만 삽입되고 포화 상태가 되버립니다.

 

2개를 삭제했는데도 불과하고 말이죠. 처음에 배열의 크기를 크게 잡아도 언젠가 끝에 도달하게 됩니다.

 

이러한 단점을 보완한 녀석이 있습니다. 원형 큐(circular queue)입니다.

 

원형 큐는 다음 글에서 다루도록 하겠습니다.