[자료구조 - C언어] 큐(Queue)

Queue - FIFO(First In First Out) 형식

 

큐(queue)는 스택과 반대로 입구와 출구가 나뉘어 있습니다.

즉, 가장 먼저 들어온 자료가 가장 먼저 나가게 되는 형식입니다. 

 

enqueue

 

dequeue

 

<queue.h>

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3
 4 typedef struct node{
 5         char value;
 6         struct node *prev;
 7         struct node *next;
 8 }NODE;
 9
10 typedef struct _queue{
11         NODE *head;
12         NODE *tail;
13 }QUEUE;
14
15 QUEUE *queue_create(){
16         QUEUE *queue;
17         queue = (QUEUE*)malloc(sizeof(QUEUE));
18
19         queue->head = NULL;
20         queue->tail = NULL;
21
22         return queue;
23 }
24
25 //HEAD IN
26 //TAIL OUT
27
28 void queue_enqueue(QUEUE *q, char value){
29
30         NODE *new_head_node = NULL;
31         new_head_node = (NODE*)malloc(sizeof(NODE));
32
33         new_head_node->value = value;
34         new_head_node->prev = NULL;
35         new_head_node->next = NULL;
36
37         if(q->head == NULL){
38                 q->head = new_head_node;
39                 q->tail = new_head_node;
40
41                 return;
42         }
43
44         q->head->prev = new_head_node;
45         new_head_node->next = q->head;
46         q->head = new_head_node;
47
48         return;
49 }
50
51 void queue_dequeue(QUEUE *q, char *value){
52
53         NODE *new_tail_node;
54
55         *value = q->tail->value;
56         q->tail = q->tail->prev;
57
58         return;
59 }

* QUEUE, NODE = 구조체

 

• QUEUE (line 10-13)

head와 tail을 관리하는 구조체 

 

• queue_create(line 15-23)

QUEUE의 메모리를 할당받아 head와 tail을 NULL로 설정함.

 

• queue_enqueue(line 28-49)

들어오는 순서대로 자료를 저장해야 하므로 NODE 타입의 new_head_node의 메모리를 할당 받음.

value, prev, next의 값을 설정함.

head가 NULL일 경우와 아닐 경우로 나눠 head와 tail의 자료를 지정함.

 

• queue_dequeue(line 51-59)

자료를 들어온 순서대로 빼주는 기능을 하기 때문에 메모리를 할당받을 필요 없음.

value의 주소 값에 tail값을 대입해주고, 원래 tail의 이전 노드를 tail로 지정하여 값을 하나씩 내보냄.

 

 

<main.c>

 1 #include <stdio.h>
 2 #include "queue.h"
 3
 4 int main(int argc, char *argv[]){
 5
 6         QUEUE *myq;
 7         char c;
 8
 9         myq = queue_create();
10
11         for(c = 'A'; c < 'Z'; c++){
12                 queue_enqueue(myq, c);
13                 printf("enqueue : %c\n", c);
14         }
15
16         printf("================================\n");
17
18         while(myq->head != NULL){
19                 queue_dequeue(myq, &c);
20                 printf("dequeue : %c\n", c);
21         }
22
23         return 0;
24 }

 

<결과창>

enqueue, dequeue 순서 출력 

 

다음 글에서는 Bubble Sort에 대해 설명하겠습니다.

감사합니다!

 

2021.08.25