[C언어] Queue

Queue 자료구조는 처음 영화관에 들어간 사람이 가장 먼저 티켓을 받는것과 비유할 수 있다. 즉 Queue는 FIFO(First In First Out)구조이다. 

위 그림에서 보는바와 같이 Queue에 데이터를 집어넣는 것을 "EnQueue"라고 하고 Queue에서 데이터를 빼는 것을 "DeQueue"라고 한다.

Key Words

EnQueue : Queue에 요소를 추가한다.
DeQueue : Queue에 요소를 제거한다.
IsEmpty : Queue가 비어있는지 확인한다.
IsFull : Queue가 가득찼는지 확인한다.
참고 
Peek : Queue에서 요소를 제거하지 않고 요소를 Get 한다.

동작 원리

1. "Front"와 "Rear" 두개의 포인터는 각각 Queue의 처음과 마지막을 의미한다.
2. Queue를 초기화 할 때 "Front"와 "Rear"를 각각 -1로 초기화 한다.
3. Enqueue를 할 때 "Rear" 인덱스를 증가시켜 요소를 Queue에 넣는다.
4. Dequeue를 할 때 "Front" 인덱스를 증가시켜서 Queue에서 요소를 제거한다.
5. Enqueue할때에는 Queue가 가득 찼는지를 반드시 확인해야 한다. (IsFull)
6. Dequeue할때에는 Queue가 비어있지 않는지를 반드시 확인해야 한다. (IsEmpty)
7. Enqueue를 처음 시작할때 "Front"값은 0으로 초기화 한다.
8. 마지막으로 Dequeue를 할때에는 "Front"값과 "Rear"값을 각각 -1로 Set해준다.

전체 소스

Header (queue.h)

1 #include <stdio.h> 2 #define SIZE 50 3 typedef struct Queue{ 4 int items[SIZE]; 5 int front; 6 int rear; 7 }Queue; 8 9 Queue* createQueue(); 10 void enQueue(Queue* queue, int data); 11 int deQueue(Queue* queue); 12 int isEmpty(Queue* queue); 13 int isFull(Queue* queue); 14 void printQueue(Queue* queue);

line 9 : Queue를 초기화 하는 함수
line 14 : Queue를 출력하는 함수

queue.c

1 #include <stdio.h> 2 #include<stdlib.h> 3 #include <queue.h> 4 5 Queue* createQueue(){ 6 Queue* newQueue = (Queue*)malloc(sizeof(Queue)); 7 newQueue->front = -1; 8 newQueue->rear = -1; 9 return newQueue; 10 } 11 12 void enQueue(Queue* queue, int data){ 13 14 if(isFull(queue)){ 15 return; 16 } 17 else{ 18 if(queue->front == -1){ 19 queue->front = 0; 20 } 21 queue->rear++; 22 queue->items[queue->rear] = data; 23 24 } 25 } 26 27 int deQueue(Queue* queue){ 28 int item = 0; 29 if(isEmpty(queue)) 30 return; 31 else{ 32 if(queue->front >= queue->rear){ 33 queue->front = -1; 34 queue->rear = -1; 35 } 36 item = queue->items[queue->front]; 37 queue->front++; 38 } 39 printf("Dequeue : %d\n", item); 40 return item; 41 } 42 43 int isEmpty(Queue* queue){ 44 45 if(queue->rear == -1) 46 return 1; 47 else 48 return 0; 49 } 50 51 int isFull(Queue* queue){ 52 if(queue->front = 0 && queue->rear == SIZE - 1) 53 return 1; 54 else 55 return 0; 56 } 57 58 void printQueue(Queue* queue){ 59 60 int i=0; 61 if(queue->rear == -1) 62 return; 63 for(i=queue->front; i<=queue->rear; i++){ 64 printf("%d ", queue->items[i]); 65 } 66 printf("\n"); 67 } 68 69 int main(void) 70 { 71 Queue* queue = createQueue(); 72 73 enQueue(queue, 1); 74 enQueue(queue, 2); 75 enQueue(queue, 3); 76 enQueue(queue, 4); 77 enQueue(queue, 5); 78 enQueue(queue, 6); 79 enQueue(queue, 7); 80 enQueue(queue, 8); 81 enQueue(queue, 9); 82 enQueue(queue, 10); 83 84 printQueue(queue); 85 deQueue(queue); 86 deQueue(queue); 87 88 printQueue(queue); 89 return 0; 90 }

Enqueue
line 14 : Enqueue를 하기 전에 Queue가 가득 찼는지 확인한다.
line 18 : 처음 Enqueue를 할때에는 Queue의 Front값을 0으로 set해준다.
line 21 : Enqueue를 할때에는 Rear 인덱스를 증가시켜 준다.
line 22 : 증가된 Rear 인덱스에 Enqueue할 데이터값을 넣는다.

Dequeue
line 29 : Dequeue를 하기 전에 Queue가 비어있지는 않는지 확인한다.
line 32 : Queue의 Front 값이 Rear값보다 크거나 같으면 모든 데이터를 Dequeue했다는 뜻이므로 Queue의 Front값과 Rear값을 -1로 초기화 해준다. 
line 36 : item 변수에 Dequeue할 값을 넣어준다. 
line 37 : Dequeue를 할때에는 Front의 인덱스를 증가시켜준다.

결과 화면

참고 문헌 : https://www.programiz.com/dsa/queue

[출처] [C언어] Queue|작성자 프로그래밍공부