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. 실행 결과