원형 큐(Circular Queue)

[선형 큐의 문제점]

- 큐에 원소가 삭제되고 나면 사용했던 저장 공간은 더 이상 재사용이 안된다.

- 큐의 저장 공간을 아무리 크게 확보하더라도 언젠가는 저장 공간이 고갈된다.

원형 큐: queue를 원형으로 취급하는 큐.

front는 마지막으로 삭제된 원소의 위치를 가리키고, rear은 마지막으로 삽입된 위치를 가리키게 되므로, 원형 큐에서는 (MAX_QUEUE_SIZE-1)개의 공간만 사용.

[소스 코드]

#define MAX_QUEUE_SIZE 10
#define TRUE 1;
#define FALSE 0;

typedef struct {
	int data;
} element;

element queue[MAX_QUEUE_SIZE];
int rear = 0;
int front = 0;

int isFull() {
	if(((rear+1)%MAX_QUEUE_SIZE) == front) {
		printf("Queue is Full!\n");
		return TRUE;
	}

	return FALSE;
}

int isEmpty() {
	if(front == rear) {
		printf("Queue is Empty!\n");
		return TRUE;
	}

	return FALSE;
}

int addQ(element item) {
	if(isFull()) {
		return FALSE;
	}
	rear = (rear+1)%MAX_QUEUE_SIZE;
	queue[rear] = item;
	
	return TRUE;
}

element deleteQ() {
	element item;

	if(isEmpty()) {
		exit(1);
	}

	front = (front+1)%MAX_QUEUE_SIZE;
	item = queue[front];
	return item;
}

int main() {
	int i;

	for(i=0; i<10; i++) {
		element item;
		item.data = i;
		if(addQ(item)) {
			printf("AddQ: %d\n", item.data);
		}
	}

	for(i=0; i<9; i++) {
		element item = deleteQ();
		printf("deleteQ: %d\n", item.data);
	}

	for(i=0; i<10; i++) {
		element item;
		item.data = i;
		if(addQ(item)) {
			printf("AddQ: %d\n", item.data);
		}
	}

	return 0;
}

[결과]