C언어 큐(Queues in C) - 연결리스트로 구현(The implementation with the linked lists)

C언어 큐(Queues in C) - 연결리스트로 구현(The implementation with the linked lists)

- 큐에 대한 내용은 이전 글 참고

1. 동작 원리

(1) 최근 노드를 가르키는 HEAD 포인터와 가장 오래된 노드를 가르키는 TAIL 포인터 초기화

(2 - 1) 삽입 명령 시 새로운 노드를 생성하고, 데이터를 입력한다.

(2 - 2) TAIL 포인터가 가르키는 노드가 없을 경우(= 큐가 비어있을 경우)

(2 - 2) HEAD와 TAIL이 새로운 노드를 가리킨다.

(2 - 3) 가르키는 노드가 있을 경우, HEAD의 위치를 갱신하면서 새로운 노드를 추가한다.

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

(3 - 2) 큐에 노드가 있을 경우에 TAIL은 그 다음 노드를 가르킨다.

(3 - 3) 삭제할 노드의 데이터를 반환하고, 노드를 제거 한다.(메모리 반납)

2. 함수 설명

int queue_empty( QUEUE *) : 큐가 비어있는지(=TAIL이 가르키는 노드가 없는지) 확인한다.

void enqueue( QUEUE **, QUEUE **, int) : 큐에 새로운 노드를 삽입한다.

int dequeue( QUEUE **) : 큐에서 가장 오래된(=가장 먼저 삽입된) 노드를 제거하고 값을 반환한다.

 

3. 전체 소스 코드

#include <stdio.h> #include <malloc.h> typedef struct queue{     int data;     struct queue *next; }QUEUE; int queue_empty( QUEUE *); void enqueue( QUEUE **, QUEUE **, int); int dequeue( QUEUE **); int main( void) {     QUEUE *H; // HEAD     QUEUE *T; // TAIL     // initialize the front and rear.    H    = NULL;    T    = NULL;    enqueue( &H, &T, 10);    enqueue( &H, &T, 20);    dequeue( &T);    dequeue( &T);    dequeue( &T);    enqueue( &H, &T, 40);    enqueue( &H, &T, 50);    enqueue( &H, &T, 30);    dequeue( &T);    dequeue( &T);    dequeue( &T);    dequeue( &T); } /*     queue_empty( QUEUE)     This function check whether the queue is empty. */ int queue_empty( QUEUE *t) {     if( t == NULL)         return 1;     return 0; } /*     enqueue( QUEUE *, int)     insert a data into the queue */ void enqueue( QUEUE **h, QUEUE **t, int data) {     QUEUE *new_q    = (QUEUE *)malloc(sizeof(QUEUE));     printf("ENQUEUE : %d\n", data);     new_q->data = data;     new_q->next = NULL;     if( *t  == NULL)     {         *h  = new_q;         *t  = new_q;         return;     }     // update the tail     (*h)->next  = new_q;     *h          = new_q; } /*     dequeue( QUEUE *)     remove a data from the queue and     return the data. */ int dequeue( QUEUE **t) {     QUEUE *temp = *t;     int data;     if( queue_empty( *t))     {         printf("the queue is empty!\n");         return -1;     }     data    = temp->data;     printf("DEQUEUE : %d\n", data);     *t      = temp->next;     free( temp);     return data; }

 

 

4. 실행 결과