원형 큐 자료구조와 큐 출력

선형큐

큐는 들어온 순서대로 처리되어 나가는 자료구조다. 배열 기반 큐의 구조체 정의는 다음과 같다.

#define MAX_Q_SIZE 10	// 큐의 최대 크기

typedef int elem_t;
typedef struct queue_t {
	elem_t data[MAX_Q_SIZE];
	int front;
	int rear;
} queue_t;

여기서도 요소타입을 typedef int element;와 같이 선언하였음을 확인할 수 있다. 위와 같이 정의된 큐의 데이터에 대해 적용가능한 기능을 다음과 같이 함수 선언으로 미리 정의한다. (이것을 추상데이터타입(ADT)이라고 한다)

void init(queue_t* q);
int is_full(queue_t* q);
int is_empty(queue_t* q);
void enqueue(queue_t* q, elem_t item);
elem_t dequeue(queue_t* q);

여기서도 enqueue나 dequeue에서 element라는 타입이름을 쓴 것을 확인할 수 있다. 요소타입을 나타내는 element를 typedef에서 바꾸면 이 함수들도 그에 따라 요소 타입을 바꿀 수 있게 된다. 이상의 부분을 헤더 파일에 넣고 C 파일에서 인클루드해 주도록 프로젝트를 구성하면 좋다. 그러면 요소 타입이 바뀔 때 헤더의 typedef 부분을 바꾸어 주어야 한다.

여기서 enqueue와 dequeue 함수를 잠깐 살펴보자.

void enq(queue_t* q, elem_t item)
{
	if (is_full(q)) {
		error("큐가 포화상태입니다.");
	}
	q->data[++(q->rear)] = item;
}

elem_t deq(queue_t* q)
{
	if (is_empty(q)) {
		error("큐가 공백상태입니다.");
	}
	return q->data[++(q->front)];
}

이와 같이 선언한 큐를 선형 큐(linear queue)라고 한다. 선형 큐는 rear가 점점 증가해서 큐의 크기가 꽉 차면 더이상 넣을 수 없게 되는데, 문제는 이 때 front 앞에 이미 처리된 것들이 나간 빈 자리가 있는데도 활용할 수가 없다는 점이다.

원형큐

위의 문제를 해결하기 위해서 rear가 증가하다가 큐의 마지막까지 가면 다시 앞에서부터 빈 자리에 채워넣을 수 있게 하는 것이 원형 큐(circular queue)다. 원형큐라면 enqueue와 dequeue에서 끝에 도달한 경우 다시 앞에서부터 시작하게 해주어야 한다. 

원형큐에서는 rear가 배열 마지막 칸 다음에 첫번째 칸으로 진행한다

그러면 원형큐는 enq와 deq가 달라져야 되는데 front나 rear의 인덱스가 MAX_Q_SIZE가 되면 0으로 새로 시작하게 바꾸어 주어야 한다. 이것을 나머지 연산(%)으로 처리할 수 있다.

// 삽입 함수
void enq(queue_t* q, elem_t item)
{
	if (is_full(q))
		// 큐가 포화상태임
	q->rear = (q->rear + 1) % MAX_Q_SIZE;
	q->data[q->rear] = item;
}

// 삭제 함수
elem_t deq(queue_t* q)
{
	if (is_empty(q))
		// 큐가 공백상태임
	q->front = (q->front + 1) % MAX_Q_SIZE;
	return q->data[q->front];
}

그리고 원형 큐가 비었는지, 꽉 찾는지 검사하는 것도 달라져야 한다.

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

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

원형큐에서는 front와 rear가 같으면 큐가 비어있다고 본다. 그리고 이와 구별하기 위해 큐가 꽉찬 상태는 배열에서 한칸 비어있는 상태로 표현한다. 즉 front는 deq할 직전 칸을 가리키고 rear는 enq한 칸을 카리킨다. 그러므로 다음에 enq할 칸은 +1을 해주어야 하는데 이 때 그것이 front와 같으면 원형큐는 풀이 된다. (하늘색은 front, 노란색은 rear다)

위 그림은 배열 기반의 원형큐의 동작을 보여준다. rear가 마지막 칸을 지나서 첫번째 칸으로 이동하는 것을 볼 수 있다. 또한 여기서 한가지 언급할 것은 front에서 나간 값은 지워지지 않고 그대로 있다는 점이다. 단지 front가 증가하므로써 그 값은 쓰레기가 된다. (그림에서 회색 글자로 표시된 데이터 부분) 프로그램에서는 많은 경우 사용한 메모리의 값을 청소하지 않고 그냥 둔다. 그러므로 사용하는 사람이 뭔가 값을 기록하면서 그 값은 의미있는 데이터가 되고 그 전에는 쓰레기 값이 들어있음을 항상 유념해야 한다. 

이러한 원형큐를 출력하는 함수를 생각해 보자. 큐의 크기에 대해 front와 rear를 표시하고 원형 큐의 상태를 출력하는 코드 부분은 다음과 같다.

	for (int i = 0; i < MAX_Q_SIZE; i++) {
		if (i == (q->front + 1) % MAX_Q_SIZE) printf("<<");
		else printf("  ");
		if (q->front < q->rear) {
		    if (q->front < i && i <= q->rear)
			 printf("%2d", q->data[i]); 
		    else
			printf("__");  
		} else if (q->rear < q->front) {
		    if (i <= q->rear || q->front < i)
			printf("%2d", q->data[i]);
		    else
			 printf("__");
		}
		if (i == q->rear) printf(" <-");
		else printf("   ");
	}

길이 5인 원형큐에서 enq와 deq의실행결과를 보여주는 출력 화면