[자료구조]원형 큐(Circular queue)

원형 큐의 구조

 

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

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

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

그림 1. 원형 큐의 구조

 

원형 큐의 삽입, 삭제

 

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

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

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

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

그림 2. 원형 큐의 삽입, 삭제

그림 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;
}

그림 3. 출력 결과