[자료구조] 원형 큐(Circular Queue)란?

큐란?

큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First in First out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

스택은 아래 부분이 막히고 윗 부분이 뚫린 통과 같았다면, 큐는 양 쪽이 뚫린 통과 같다. 스택이 가장 윗부분에서 데이터를 넣고 꺼냈다면, 큐는 front에서 dequeue 연산이 진행되고, rear 부분에서 enqueue 연산이 진행된다.

 

원형큐란?

원형 큐에서는 front와 rear의 개념이 약간 변한다. 초기 값은 -1이 아니라 front와 rear가 같은 위치를 가리키기만 하면 된다. front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막으로 입력된 요소를 가리킨다.

---

원형큐의 과정

1. 처음에 front, rear는 모두 0을 가리킨다.
2. enqueue(A) 연산은 먼저 rear를 증가키시고  증가된  위치에  데이터  A를 삽입한다.
3. enqueue(B)  연산을  통해  rear는 2가 되었다.
4. 삭제 연산 dequeue() 에서는 먼저 front를 증가시키고 증가된 위치에서 데이터를 꺼낸다.
5. front는 1이 되었다. 삽입과 삭제가 아무리 반복되어도 선형 큐에서와 같은 요소들의 이동이 필요가 없다.
6. front와 rear의 값이 계속 증가하다가 7이 되면 다음 값은 0이 되어 배열의 범위 안에서 계속 움직이기 때문이다.

---

원형큐의 공백과 포화 구분

• front와 rear의 값이  같으면  원형  큐가 비어  있는  공백  상태이다.
• 포화  상태를  판단해봐야  하는데  원형  큐에서는  하나의  자리는 항상  비워둬야  한다.
• 그렇게  해야만  포화  상태와  공백  상태를  구별할  수 있기  때문이다.
• 만약 한 자리를 비워두지 않으면 공백상태와 포화 상태의 front==rear식이 같아 구분할 수 없기 떄문이다.
• 따라서 원형 큐에서 front == rear 이면 공백이고 front가 rear보다 하나 앞에 있으면 포화 상태가 된다.

front == (rear + 1) % MAX_QUEUE_SIZE

C언어 구현

큐는 배열 혹은 연결리스트로 구현할 수 있다. 배열로 구현할 시에는 여러가지 문제점이 발생할 수 있다. 하지만, 여기서는 원형큐이므로 배열로 구현할 수 있다.

1. 노드 정의 및 큐 초기화

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

// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

 

2. isEmpty() 함수 및 isFull() 함수

// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == q->rear);
}

front 와 rear의 값이 같으면 큐가 비어있다는 뜻이다.

// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

front의 값이 rear+1와 같다면 즉, rear의 다음 칸이 front라면 큐는 꽉찼다는 뜻이다. 모듈러 연산을 하는 이유는 원형큐에서 2,3,4... 바퀴에도 계속 동일한 인덱스를 가지기 위함이다.

 

3. 큐의 삽입(enqueue)

void enqueue(QueueType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

4. 큐의 데이터 반환(dequeue)

element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}