[C] Queue 배열로 구현

[C] Queue 배열로 구현

Queue는 스택과 반대로 먼저 들어온 데이터가 먼저나가는 FIFO(First In First Out) 구조이다.

큐를 배열로 구현할 때는, Overflow를 주의해야 한다.

큐는 put과 get이 다른 통로로 구성되어 있기 때문에 배열에서 자료가 들어오는(put) rear 와 자료가 나가는(get) front의 포인터를 유지한다.

하지만 put()과 get()이 발생하면서 front 와 rear 포인터는 계속적으로 증가하고 제한된 크기의 배열을 넘어가게 된다.

이러한 문제를 막기위해 배열의 마지막+1 은 0 으로 전환해주는 원형 큐를 사용하기도 한다.

원형 큐를 사용할 때 주의할 점은, rear의 포인터는 마지막 자료가 아닌 put() 수행시 들어올 자료의 공간을 가리킨다.

이것은 큐가 꽉찼는지 또는 비어있는지 구분하기 위함이다.

front == rear 라면 큐가 비어 있는 것이며, (rear+1) % MAX == front 이면 큐가 꽉차있는 것이다.

rear 가 하나의 공간을 차지하고 있기 때문에, 큐에 저장할 수 있는 자료의 갯수는 배열의크기(MAX)-1 이다.

#include <stdio.h> #define MAX 10 int queue[MAX]; int front, rear; void init_queue(void){     front = rear = 0; } void clear_queue(void){     front = rear; } int put(int k){     // 큐가 꽉차있는지 확인     if ((rear + 1) % MAX == front){         printf("\n   Queue overflow.");         return -1;     }     queue[rear] = k;     rear = ++rear % MAX;     return k; } int get(void){     int i;     if (front == rear){         printf("\n  Queue underflow.");         return -1;     }     i = queue[front];     front = ++front % MAX;     return i; } void print_queue(void){     int i;     printf("\n Queue contents : Front ----------> Rear \n");     for (i = front; i != rear; i = ++i%MAX)         printf("%-6d", queue[i]); } void main(void){     int i;     init_queue();     printf("\nPut 5, 4, 7, 8, 2, 1");     put(5);     put(4);     put(7);     put(8);     put(2);     put(1);     print_queue();     printf("\nGet");     i = get();     print_queue();     printf("\n  getting value is %d ", i);     printf("\nPut 3, 2, 5, 7");     put(3);     put(2);     put(5);     put(7);     print_queue();     printf("\nNow queue is full, put 3");     put(3);        // 오버플로우 에러    배열 크기는 10이지만 9개만 저장할 수 있다     print_queue();     printf("\nInitialize queue");     clear_queue();     print_queue();     printf("\nNow queue is empty, get");     i = get();     print_queue();     printf("\n getting value is %d", i);     return 0; }

출처: https://hyeonstorage.tistory.com/349?category=622873 [개발이 하고 싶어요]