[자료구조] Queue(큐) C언어로 구현하기 - 2 (원형 큐)

선형 큐의 단점을 보완하여 나오게 된 원형큐(Circular Queue)

---

원형 Queue의 구현 과정(C언어)

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

typedef struct {
	int front, rear;
	int capacity;
	int size;		// 큐에 들어간 요소의 수를 새롭게 선언
	int* array;		// int를 요소로 받는 큐 array
} Queue;

원형 큐의 구조체에는 size가 새롭게 선언됨

size: 큐에 들어가있는 요소의 개수

 

Queue* createQueue(int capacity) {
	Queue* queue = (Queue*)malloc(sizeof(Queue));

	// queue 할당 실패시 NULL 반환
	if (!queue)
		return NULL;

	queue->size = 0;	// queue에 size를 새롭게 정의
	queue->front = 0;
	queue->rear = -1;
	queue->capacity = capacity;
	queue->array = (int*)malloc(capacity * sizeof(int));

	// array 할당 실패시 NULL 반환
	if (!queue->array)
		return NULL;

	return queue;
}

원형 큐를 선언하는 함수

선언할 때에는 요소가 없으므로 size를 0으로 초기화함

 

int isFull(Queue* queue) {
	return (queue->size == queue->capacity);
}

큐에 요소가 가득 찼는지 확인하는 함수

rear + 1 == front 여도 가득 차 있다고 표현할 수 있지만, size를 통해서 확인하는게 더 직관적임

 

int isEmpty(Queue* queue) {
	return (queue->size == 0);
}

마찬가지로 size를 통해 큐가 비어있는지를 확인

 

void enqueue(Queue* queue, int new_element) {
	// 큐가 가득 차 있지 않으면 rear에 요소 추가
	if (!isFull(queue)) {
		queue->rear = (queue->rear + 1) % queue->capacity;
		queue->array[queue->rear] = new_element;
		queue->size += 1;
	}
	// 큐가 가득 차 있으면 출력
	else
		printf("Queue is Full!\n");
}

큐가 가득 차 있지 않으면 enqueue 과정을 진행

이 때, rear의 값은 1을 더한 후에 큐의 크기로 나눈 나머지 값과 같음

이후 rear값에 새로운 요소를 넣음

 

int dequeue(Queue* queue) {
	// 큐가 비어있지 않으면 front에서 요소 빼고 리턴
	if (!isEmpty(queue)) {
		// dequeue 전 front의 요소를 element에 저장
		int element = queue->array[queue->front];
		queue->front = (queue->front + 1) % queue->capacity;
		queue->size -= 1;
		return element;
	}
	// 큐가 비어있으면 출력
	else
		printf("Queue is Empty!\n");
	return -1;
}

큐가 비어있지 않으면 dequeue과정을 진행

이 때, front의 값은 1을 더한 후에 큐의 크기로 나눈 나머지 값과 같음

이후 dequeue 이전 front 값을 리턴함