C언어 큐(Queues in C) - 배열로 구현(The implementation with the array)

C언어 큐(Queues in C) - 배열로 구현(The implementation with the array)

- FIFO(First In First Out) 정책을 사용한다.

- 먼저 삽입된 데이터가 먼저 나온다.

- 선형 큐의 경우 큐의 포화상태와 빈(empty)상태를 구분하지 못한다.

( 이를 해결하기 위해 환형 큐가 고안 되었다. )

- 삽입 명령을 ENQUEUE라고 부른다.

- 삭제 명령을 DEQUEUE라고 부른다.

1. 동작 원리

(1) 삽입할 위치를 가리키는 head와 내보낼 위치를 가르키는 tail의 위치를 초기화 한다.

(2) 삽입 명령 시 head가 가르키는 곳에 큐의 위치에 데이터를 입력하고 head의 값을 증가시킨다.

(3 - 1) 삭제 명령 시 큐가 비어있는지 확인한다.

(3 - 2) 큐에 데이터가 있다면, 해당 데이터를 반환하고 tail의 값을 증가시킨다.

[ Fig. 1 ] process of the queue, site : introduction to algorithms 3/E

 

2. 함수 설명

int queue_empty( QUEUE) : 큐가 비어있는지 확인하는 기능을 수행한다.

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

int dequeue( QUEUE *) : 큐에서 데이터를 제거하는 것으로 동작원리 (3)에 해당한다.

3. 전체 소스 코드

#include <stdio.h> #define MAX     10 typedef struct queue{     int head;     int tail;     int ar[MAX]; }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, 30);     enqueue( &Q, 20);     enqueue( &Q, 50);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q);     dequeue( &Q); } /*     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) {     q->ar[q->head++]    = data;     printf("ENQUEUE : %d\n", data);     q->head = q->head % MAX; } /*     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;     }     data    = q->ar[q->tail++];     printf("DEQUEUE : %d\n", data);     q->tail = q->tail % MAX;     return data; }

 

 

4. 실행 결과