[C] Circular array기반의 Queue 구현

자료구조를 처음 구현할 때, C를 사용하는 사람들은 보통 array를 많이 사용한다.

Stack과 Queue에는 원소의 위치를 가리키는 변수 top, front, rear가 존재한다.

이 때, Stack의 마지막 원소의 위치를 가리키는 top은 원소의 증감에 따라 함께 증가하고 감소하기에 문제가 없다.

 

하지만 Queue의 front와 rear는 연산을 반복하면서 값이 계속해서 증가한다.

따라서 단순한 array로 Queue를 구현하면, 원소의 push와 pop을 반복하면서 앞의 공간은 사용하지 않아 낭비되고 뒤의 공간은 부족할 수 밖에 없다.

 

출처: https://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/FIGS/queue04.gif

따라서 Circular Array를 통해 Queue를 구현하는 방법이 존재한다.

Circular Array란, 일반적으로 정의하는 선형의 array가 아니라 '배열의 마지막 인덱스 다음의 위치를 맨 첫번째'로 정의하는 array를 말한다.

위와 같은 array에서는 push와 pop을 반복해도 front와 rear의 값이 무한히 증가하는게 아니라, 다시 0으로 초기화 되었다가 증가하기 때문에 발생할 수 있는 문제를 예방할 수 있다.

 

c의 circular array를 이용해서 구현한 Queue는 다음과 같다.

#define MAX_SIZE 100

typedef struct data_type {
	int num;
}data;

typedef struct {
	data* items;
	int cnt;
	int front;
	int rear;
}Queue;

void create(Queue* q) {
	q->items = (data*)malloc(sizeof(data) * MAX_SIZE);
	q->cnt = 0;
	q->front = 0;
	q->rear = 0;
}

bool isEmpty(Queue* q) {
	if (q->cnt == 0)
		return true;
	return false;
}

bool isFull(Queue* q) {
	if ((q->front == q->rear) && (q->cnt == MAX_SIZE))
		return true;
	return false;
}

bool enqueue(Queue* q, data item) {
	if (isFull(q))return false;

	q->items[q->rear] = item;
	q->rear = (q->rear + 1) % MAX_SIZE;
	q->cnt++;
	return true;
}

data dequeue(Queue* q) {
	data item;
	if (isEmpty(q)) {
		item.num = -1;
		return item;
	}

	item = q->items[q->front];
	q->front = (q->front + 1) % MAX_SIZE;
	q->cnt--;

	return item;
}

위의 queue에서, cnt라는 변수를 추가한 이유는? circular array이기 때문에 front와 rear가 같을 때가 두 번 존재하기 때문이다(queue가 비었을 때와 꽉 찼을 때).

 

따라서 cnt라는 변수를 추가해서 두 가지 경우를 구분할 수 있게 해줬당