C언어 원형큐 배열 - ceon-eo wonhyeongkyu baeyeol

원형 큐의 구조

원형 큐는 선형 큐의 front와 rear값이 계속 증가하기만 한다는 문제점을 극복한 구조이다.

배열을 선형으로 생각하지 않고 원형으로 생각한다.

즉, front와 rear의 값이 배열의 끝인 (MAZ_QUEUE_SIZE -1)에 도달하면 다음에 증가되는 값은 0이 되도록 하는 것이다. 

원형 큐의 삽입, 삭제

원형 큐에서는 front와 rear 의 개념이 약간 변경된다. 먼저 초기 값은 -1이 아닌 0이다. 

front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다.

처음에 front, rear는 모두 0이고 삽입 시에는 rear가 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입된다. 

또 삭제 시에도 front가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제한다.

그림 2는 원형 큐의 삽입, 삭제 과정을 보여준다.

front와 rear값이 같으면 원형 큐가 비어있음을 나타낸다.

여기서 enqueue(A)를 하면 rear값이 1 증가하고 해당 위치에 A가 삽입된다.

마찬가지로 enqueue(B)를 하면 rear값이 1 증가하고 해당 위치에 B가 삽입된다.

dequeue(B)를 하면 front값이 1 증가하고 해당 위치에 있던 A가 삭제된다.

원형 큐에서는 포화 상태와 공백 상태를 구별하기 위하여 하나의 자리는 항상 비워두다.

따라서 front == rear이면 공백 상태가 되고 fornt가 rear보다 하나 앞에 있으면 포화 상태가 된다.

원형 큐의 구현

C언어로 1차원 배열 큐를 구현해보자.

MAX_QUEUE_SIZE로 큐의 사이즈를 지정해주었다.

element는 편의상 int로 선언하였다.

큐 사이즈 크기의 1차원 배열과 front, rear의 정보를 가지고 있는 QueueType구조체를 선언하였다.

#include <stdio.h>

#define MAX_QUEUE_SIZE 5

typedef int element;

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

front와 rear에 0을 넣어주는 큐 초기화 함수 init_queue를 작성하였다.

큐가 비어 있다면 front와 rear는 같다.

이를 이용하여 큐가 비어 있는지를 확인하는 함수 is_empty를 작성하였다.

큐가 가득 찼다면 (rear+1)에서 큐의 사이즈를 나눈 나머지는 front와 같을 것이다.

이를 이용하여 큐가 가득 찼는지 확인하는 함수 is_full을 작성하였다.

//큐 초기화 
void init_queue(QueueType* q) {
	q->front = q->rear = 0;
}

//큐가 비어 있는지 확인
int is_empty(QueueType* q) {
	return (q->front == q->rear);
}

//큐가 가득 찼는지 확인
int is_full(QueueType* q) {
	return (q->front == ((q->rear+1)%MAX_QUEUE_SIZE));
}

큐의 주요 연산인 enqueue, dequeue함수이다.

enqueue를 하기 전에 큐가 가득 차 있는지 확인 하고,

가득 차 있다면 메세지를 출력하고 아니라면 삽입 연산을 수행한다.

기존의 큐의 하단을 가리키고 있었던 rear에 1을 더해준 후 MAX_QUEUE_SIZE로 나눠주고 배열의 해당 인덱스에 데이터를 넣도록 작성하였다.

dequeue를 하기 전에 큐가 비어 있는지 확인 하고,

비어 있다면 메세지를 출력하고 아니라면 삭제 연산을 수행한다.

큐의 전단에 1을 더해준 후 MAX_QUEUE_SIZE로 나눠주고 해당 인덱스에 있었던 데이터를 data 변수에 대입한다.

data변수를 return한다.

//큐가 가득 차 있는지 확인 후 삽입 연산
void enqueue(QueueType* q, int data) {
	if (is_full(q)) {
		printf("Queue is full \n");
	}
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->data[q->rear] = data;
	}
}

//큐가 비어 있는지 확인 후 삭제 연산
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		printf("Queue is empty \n");
		exit(1);
	}
	else {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		int data = q->data[q->front];
		return data;
	}
}

큐의 모든 element를 출력하는 함수이다.

큐가 비어 있다면 빈 큐라는 메세지를 출력한다.

그렇지 않다면 큐를 출력한다.

//큐의 모든 요소 출력
void print_queue(QueueType* q) {
	if (is_empty(q)) {
		printf("Empty Queue \n");
	}
	else {
		printf("Queue:");
		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");
		}
	}
}

main함수에서는 QueueType을 선언해주고 각 element들을 enqueue, dequeue한 후 출력을 해 주었다.

int main() {

	QueueType queue;

	int item = 0;
	init_queue(&queue);

	enqueue(&queue, 3);
	print_queue(&queue);

	enqueue(&queue, 4);
	print_queue(&queue);

	enqueue(&queue, 5);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	enqueue(&queue, 6);
	print_queue(&queue);

	enqueue(&queue, 7);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	return 0;
}

전체 코드

#include <stdio.h>

#define MAX_QUEUE_SIZE 5

typedef int element;

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

//큐 초기화 
void init_queue(QueueType* q) {
	q->front = q->rear = 0;
}

//큐가 비어 있는지 확인
int is_empty(QueueType* q) {
	return (q->front == q->rear);
}

//큐가 가득 찼는지 확인
int is_full(QueueType* q) {
	return (q->front == ((q->rear+1)%MAX_QUEUE_SIZE));
}

//큐가 가득 차 있는지 확인 후 삽입 연산
void enqueue(QueueType* q, int data) {
	if (is_full(q)) {
		printf("Queue is full \n");
	}
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->data[q->rear] = data;
	}
}

//큐가 비어 있는지 확인 후 삭제 연산
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		printf("Queue is empty \n");
		exit(1);
	}
	else {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		int data = q->data[q->front];
		return data;
	}
}

//큐의 모든 요소 출력
void print_queue(QueueType* q) {
	if (is_empty(q)) {
		printf("Empty Queue \n");
	}
	else {
		printf("Queue:");
		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");
		}
	}
}

int main() {

	QueueType queue;

	int item = 0;
	init_queue(&queue);

	enqueue(&queue, 3);
	print_queue(&queue);

	enqueue(&queue, 4);
	print_queue(&queue);

	enqueue(&queue, 5);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	enqueue(&queue, 6);
	print_queue(&queue);

	enqueue(&queue, 7);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	return 0;
}