원형 큐 자료구조와 큐 출력
선형큐
큐는 들어온 순서대로 처리되어 나가는 자료구조다. 배열 기반 큐의 구조체 정의는 다음과 같다.
#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에서 끝에 도달한 경우 다시 앞에서부터 시작하게 해주어야 한다.
그러면 원형큐는 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(" ");
}