C언어 원형 큐(circular queues in C)

C언어 원형 큐(circular queues in C)

- 선형 큐의 문제점을 개선하기 위해 고안(= 큐의 포화 상태와 빈(empty) 상태를 구별하지 못함)

- 큐의 한 칸을 비워두고 이것을 포화 상태와 빈(empty) 상태를 구분하기 위해 사용한다.

[ Fig. 1 ] process of circular queue

 

위의 그림을 보면 (A)는 시작 부분이라 T(Tail)과 H(Head)가 동일한 위치에 있다. 즉, 이것은 큐가 비어있다는 것을 의미한다. 큐에 데이터를 삽입할 때 H가 가르키는 위치에 데이터를 삽입하게 되면 모든 큐에 데이터를 삽입했을 경우(=포화 상태) T와 H가 같은 곳을 가르키게 된다. 즉 포화 상태인지 큐가 비어있는 상태인지 알 수가 없다. 따라서 H가 가르키는 위치가 아니라 H + 1의 위치에 데이터를 삽입한다. 그리고 항상 삽입 전에 H + 1의 위치가 T의 위치가 같은지 확인한다. 만약 H + 1과 T의 위치가 같다면 포화 상태로 간주하는 것이 원형 큐의 원리이다. 사실 상 큐가 비어있지만, 저 곳에 만약 데이터를 삽입하게 된다면 앞서 설명한 것과 같이 포화 상태화 빈 상태를 구분할 수가 없기에 데이터를 덮어씌워 손실이 생길 수 있다.

(D)를 보면 H + 1은 인덱스를 초과하므로 다시 큐의 0번 인덱스를 가르킨다. 즉 H + 1과 T의 위치가 같으므로 포화 상태로 간주하여 더 이상 큐에 데이터를 입력할 수 없다.

이번에는 (F - H) 과정을 거쳐 모든 큐의 데이터를 제거하게 되면, 다시 T와 H가 같은 위치를 가르키게 된다.(= 큐가 빈(empty) 상태)

1. 동작원리

(1) 큐의 시작과 끝의 인덱스를 저장하는 head와 tail을 초기화한다.

(2 - 1) 삽입 명령이 있을 경우, 큐의 포화상태를 확인한다.

(2 - 2) 현재 (head의 위치 + 1) % MAX의 값이 tail이 가르키는 위치와 같다면 포화상태이다.

※  (head의 위치 + 1) % MAX 연산을 하는 이유는 큐의 크기를 벗어나면 다시 0부터 시작하기 위함이다.

즉, 큐의 인덱스가 0 - 3이라고 가정한다면 큐의 크기(MAX)는 4가된다.

현재 H가 3을 가르키고 있는 상황에서 + 1을 하면 4가 되므로 큐의 인덱스를 초과한다.

그러므로 큐의 크기로 나머지 연산을해서 다시 0부터 시작하게끔 만드는 것이다.

(2 - 3) 포화상태가 아닐 경우 head의 위치를 1 증가시키고 해당 위치에 데이터를 삽입한다.

(3 - 1) 제거 명령이 있을 경우, 큐가 비어있는지 확인한다.

(3 - 2) head의 위치과 tail의 위치가 같다면 비어있다는 것이다.

(3 - 3) 큐에 데이터가 있다면 tail의 위치를 1 증가시키고, 기존 데이터를 반환한다.

2. 함수 설명

int queue_full( QUEUE) : 큐가 포화상태인지 확인하는 기능으로 동작원리 (2 - 2)에 해당한다.

int queue_empty( QUEUE) : 큐가 비어있는지 확인하는 기능으로 동작원리 (3 -2)에 해당한다.

void enqueue( QUEUE *, int) : 큐에 데이터를 입력하는 기능으로 동작원리 (2)에 해당한다.

int dequeue( QUEUE *) : 큐에서 가장 먼저 삽입된 데이터를 반환해주는 기능으로 동작원리 (3)에 해당한다.

3. 전체 소스 코드

#include <stdio.h> #define MAX     5 typedef struct queue{     int head;     int tail;     int ar[MAX]; }QUEUE; int queue_full( QUEUE); int queue_empty( QUEUE); void enqueue( QUEUE *, int); int dequeue( QUEUE *); int main( void) {     QUEUE Q;     // initialize the front and rear.     Q.head  = 0;     Q.tail  = 0;     enqueue( &Q, 10);     enqueue( &Q, 20);     enqueue( &Q, 30);     enqueue( &Q, 40);     enqueue( &Q, 50);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q);     enqueue( &Q, 50);     enqueue( &Q, 60);     enqueue( &Q, 70);     enqueue( &Q, 80);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q); } /*     queue_full( QUEUE)     This function examine whether the queue is full. */ int queue_full( QUEUE q) {     if( (q.head + 1) % MAX == q.tail)     {         return 1;     }     return 0; } /*     queue_empty( QUEUE)     This function check whether the queue is empty. */ int queue_empty( QUEUE q) {     if( q.head == q.tail)     {         return 1;     }     return 0; } /*     enqueue( QUEUE *, int)     insert a data into the queue */ void enqueue( QUEUE *q, int data) {     if( queue_full( *q))     {         printf("the queue is full!\n");         return;     }     q->head     = (q->head + 1) % MAX;     q->ar[q->head]  = data;     printf("ENQUEUE : %d\n", data); } /*     dequeue( QUEUE *)     remove a data from the queue and     return the data. */ int dequeue( QUEUE *q) {     int data;     if( queue_empty( *q))     {         printf("the queue is empty!\n");         return -1;     }     q->tail = (q->tail + 1) % MAX;     data    = q->ar[q->tail];     printf("DEQUEUE : %d\n", data);     return data; }

 

 

4. 실행 결과