[Data Structure] 원형큐 (Circular Queue)

선형큐 문제점

가득 차지 않았지만, rear가 마지막 인덱스를 가리키고 있을 경우

    -> euqueue하기 위한 공간을 마련해야 하기 때문에 전체 데이터를 이동

    -> 비효율적인 작업 발생

    -> 해결 : 원형큐 

 

 

 

원형큐 (Circular Queue)

- 배열의 끝 (MAX_QUEUE_SIZE -1)에 도달하면 다음 증가되는 값 = 0

- 초기화 상태 : front = rear = 0

- front : 항상 큐의 첫 번째 요소에서 하나 전

- rear : 마지막 item의 인덱스

 

공백 상태/포화 상태를 구분하기 위해 항상 1칸은 비워둔다

• 공백 상태 : front == rear
• 포화 상태 : front가 rear보다 하나 다음 

 

 

※ Example (enqueue / dequeue 반복을 통한 인덱스 변화)

- MAX_QUEUE_SIZE = 5

front	rear	과정
0	0	초기화
0	1	enqueue
0	2	enqueue
0	3	enqueue
0	4	enqueue → 포화
1	4	dequeue
2	4	dequeue
3	4	dequeue
4	4	dequeue → 공백 (1)
4	0	enqueue (2)
4	1	enqueue
4	2	enqueue
4	3	enqueue → 포화 (3)
0	3	dequeue (4)
1	3	dequeue
2	3	dequeue
3	3	dequeue → 공백

• enqueue/dequeue를 통해서 front, rear를 1 증가시키는 경우
• (1) → (2), (3) → (4)를 살펴보면
• (1) → (2) : rear 4 → 0
• (3) → (4) : front 4 → 0

∴ 인덱스를 증가시키는 경우

→ (front+1)%MAX_QUEUE_SIZE, (rear+1)%MAX_QUEUE_SIZE를 통해서 증가

 

 

1. is_full / is_empty

int is_full(queue* q) {
	// 포화 상태 : front 인덱스가 rear 인덱스보다 하나 앞
	// front == (rear+1)%MAX_QUEUE_SIZE
	return q->front == (q->rear + 1) % MAX_QUEUE_SIZE;
}

int is_empty(queue* q) {
	// 공백 상태 : front == rear
	return q->front == q->rear;
}

- is_full

• 큐가 가득 차있으면 더이상 enqueue(삽입) 불가
• 큐가 가득 차있으면 front == (rear+1)%MAX_QUEUE_SIZE

- is_empty

• 큐가 비어있으면 더이상 pop(삭제), peek(선택) 불가
• 큐가 비어있으면 front == rear

 

 

2. enqueue (int rear)

void enqueue(queue* q, element item) {
	if (is_full(q)) {
		fprintf(stderr, "Error : Queue is full");
		return;
	}
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->queue[q->rear] = item;
	}
}

 

 

3. dequeue (int front)

element dequeue(queue* q) {
	if (is_empty(q)) {
		fprintf(stderr, "Error : Queue is empty");
		return;
	}
	else {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		return q->queue[q->front];
	}
}

 

 

4. Full Code (Circular Queue With Array)

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

#define MAX_QUEUE_SIZE 5

typedef int element;

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

int size(queue* q) {
	return MAX_QUEUE_SIZE;
}

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

int is_full(queue* q) {
	// 포화 상태 : front 인덱스가 rear 인덱스보다 하나 앞
	// front == (rear+1)%MAX_QUEUE_SIZE
	return q->front == (q->rear + 1) % MAX_QUEUE_SIZE;
}

int is_empty(queue* q) {
	// 공백 상태 : front == rear
	return q->front == q->rear;
}

void enqueue(queue* q, element item) {
	if (is_full(q)) {
		fprintf(stderr, "Error : Queue is full");
		return;
	}
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->queue[q->rear] = item;
	}
}

element dequeue(queue* q) {
	if (is_empty(q)) {
		fprintf(stderr, "Error : Queue is empty");
		return;
	}
	else {
		q->front = (q->front + 1) % MAX_QUEUE_SIZE;
		return q->queue[q->front];
	}
}

element peek(queue* q) {
	if (is_empty(q)) {
		fprintf(stderr, "Error : Queue is empty");
		return;
	}
	else 
		return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}

void queue_print(queue* q) {
	printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		element item = q->front;
		do {
			item = (item + 1) % MAX_QUEUE_SIZE;
			printf("%d |	", q->queue[item]);
			if (item == q->rear)
				break;
		} while (item != q->front);
	}
	printf("\n");
}

int main(void) {
	queue q;
	init_queue(&q);
	element item;

	printf("Queue Size : %d\n\n", size(&q));

	printf("---데이터 삽입 enqueue---\n");
	while (!is_full(&q)) {
		printf("삽입할 item 입력 : ");
		scanf("%d", &item);
		enqueue(&q, item);
		queue_print(&q);
	}
	printf("Queue is full\n\n");

	printf("---데이터 삭제 dequeue---\n");
	while (!is_empty(&q)) {
		item = dequeue(&q);
		printf("pop된 item : %d\n", item);
		queue_print(&q);
	}
	printf("Queue is empty\n\n");

	return 0;
}