C - 자료구조 큐

큐(queue)
선입선출 방식을 이용한 데이터 타입이며 이와 같은 입출력 형태를 First-In First-Out으로 FIFO라고 한다.

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다.
스택은 삽입과 삭제가 같은 쪽에서 이루어지지만 큐는 다른쪽에서 일어난다.
큐에서 삽입이 일어나는 곳은 후단(rear)이라 하고 삭제가 일어나는 곳을 전단(front)이라 한다.

큐의 기본 형태

객체 : 0개이상의 요소들로 구성된 선형 리스트

연산 : 
	creat(max_size) :
    	최대 크기가 max_size인 공백큐를 생성
    init(q):
    	큐를 초기화
    is_empty(q):
    	if(size ==0) return TRUE;
        else return FALSE;
   	is_full(q):
    	if(size==max_size) return TRUE;
    else return FALSE;
    enqueue(q, e):
    	if(is_full(q)) queue_full 오류;
        else q의 끝에 e를 추가한다
    dequeue(q):
    	if(is_empty(q)) queue_empty 오류;
        else q의 맨 앞에 있는 e를 제거하여 반환한다
    peek(q):
    	if(is_empty(q)) queue_empty 오류;
        else q의 맨 앞에 있는 e를 읽어서 반환한다

큐의 핵심은 front와 rear의 초기값은 -1이다. 데이터가 증가되면 rear가 하나 증가하고 그 위치에 데이터를 저장한다.
삭제할때에도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다.

허나 이러한 선형큐에서는 문제점이 하나 발생한다.
데이터를 삭제해도 언젠가는 그 배열의 끝에 도달하여 앞부분의 공백이 존재하고 계속 비워둬야하거나 재정렬이 필요한 단점이 있다.

그래서 우리는 원형큐를 사용한다.
앞의 큐와 다른점은 front의 초기값은 -1이 아닌 0을 가리키는 것이다.
또한 front는 항상 큐의 첫번째 요소의 하나 앞을, rear은 마지막 요소를 가리킨다.
데이터의 삽입시 rear가 먼저 증가되고, 그 위치에 새로운 데이터를 저장한다.
데이터의 삭제시에는 front가 먼저 증가된 다음, 그 위치의 데이터를 삭제한다.
그리고 원형큐에서 하나의 자리는 항상 비워둔다. 왜냐하면 포화 상태와 공백 상태를 구별하기 위해서이다.
자 그럼 이러한 배열을 어떻게 원형으로 회전시켜 삽입 또는 삭제를 처리할까?
front와 rear를 원형으로 회전시키기 위해서는 나머지 연산자 %를 이용해야 한다.

front <- (front+1) % MAX_QUEUE_SIZE
rear <- (rear+1) % MAX_QUEUE_SIZE

위의 코드를 토대로 MAX_QUEUE_SIZE가 5라고 가정하였을 시 front와 rear 값은 0,1,2,3,4,0,1 ..... 순으로 회전하는 것을 확인 할 수 있다.
즉 front==rear은 공백상태 front가 rear보다 하나 앞에 있으면 포화상태이다.

아래는 원형큐의 기본적인 틀이다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5


typedef int element;
typedef struct{
    element data[MAX_SIZE];
    int front, rear;
}QueueType; //큐 구조체 선언

void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
} //에러 메세지 출력

void init_queue(QueueType *q){
    q->front=0;
    q->rear=0;
} //큐 초기화

int is_empty(QueueType *q){
    return (q->front == q->rear);
} //front와 rear값이 같을 경우 비어 있음

int is_full(QueueType *q){
    return ((q->rear+1) % MAX_SIZE == q->front);
} //rear+1값 % MAX_SIZE 의 결과 값이 front의 값과 같을 경우 꽉 차있는 것

void enqueue(QueueType *q, element item){
    if (is_full(q))
        error("큐가 포화상태 입니다.");
    q->rear = (q->rear+1) % MAX_SIZE; //rear를 1 증가시킨 위치로 옮기고
    q->data[q->rear] = item; //새로운 값을 data에 담는다
}

element dequeue(QueueType *q){
    if(is_empty(q)) 
        error("큐가 공백 상태 입니다.");
    q->front = (q->front+1) % MAX_SIZE; //front를 1 증가시킨 위치로 옮기고
    return q->data[q->front]; //front위치에 있는 데이터를 반환한다
}

element peek(QueueType *q){
    if (is_empty(q))
        error("큐가 공백 상태 입니다.");
    return q->data[(q->front+1)%MAX_SIZE]; //front위치를 1증가시키고 그 값을 반환함
}

int main(){
    


   return 0;
}

위의 코드를 이용해 간단히 확인해보면

int main(){

    QueueType queue;
    int element;
    init_queue(&queue);
    printf("---데이터 추가 단계---\n");
    while(!is_full(&queue)){
        printf("정수를 입력하세요 : ");
        scanf("%d", &element);
        enqueue(&queue, element);
    }
    printf("큐는 포화상태입니다. \n\n");

    printf("---데이터 삭제 단계---\n");

    while(!is_empty(&queue)){
        element = dequeue(&queue);
        printf("꺼내진 정수 : %d \n", element);
    }
    printf("큐는 공백 상태 입니다 ! !  \n");


   return 0;
}

츨력 결과

---데이터 추가 단계---
정수를 입력하세요 : 5
정수를 입력하세요 : 6
정수를 입력하세요 : 7
정수를 입력하세요 : 8
큐는 포화상태입니다. 

---데이터 삭제 단계---
꺼내진 정수 : 5 
꺼내진 정수 : 6 
꺼내진 정수 : 7 
꺼내진 정수 : 8 
큐는 공백 상태 입니다 ! !

MAX_SIZE가 5이기에 데이터는 총 4개의 값이 담기는 것을 확인할 수 있다.

원형큐의 기본 형태

#include <stdio.h>
#include <stdlib.h>

//원형큐

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct{
    element data[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

void init_queue(QueueType *q){
    q->rear = 0; //원형큐는 rear, front의 초기값이 0이다
    q->front = 0;
}

int is_full(QueueType *q){
    return ((q->rear+1)%MAX_QUEUE_SIZE == q->front); 
    //rear+1을 나머지 연산한 값이 front와 같다면 큐는 포화상태
}

int is_empty(QueueType *q){
   return (q->rear == q->front);
   //front와 rear값이 같다면 공백 상태이다
}
void queue_print(QueueType *q){
    printf("QUEUE(front = %d rear = %d)",q->front, q->rear);
    if(!is_empty(q)) {
        int i =q->front;
        do{
            i=(i+1) % MAX_QUEUE_SIZE;
            printf("%d | ", q->data[i]);
            if(i==q->rear) break;
        }while(i!=q->front);
    }
    printf("\n");
}


void enqueue(QueueType *q, int item){
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
    //rear 값은 rear+1의 값을 나머지 연산한 위치를 가리키게 하며
    //변경된 rear에 데이터 저장
}

int dequeue(QueueType *q){
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
    //front의 값을 front+1의 값을 나머지 연산한 위치를 가리키게 하여
    //그 안의 데이터를 반환함
}

int peek(QueueType *q){
    return q->data[(q->front+1)%MAX_QUEUE_SIZE];
    //front+1을 나머지연산한 값의 위치에 데이터를 반환함
}


int main(){
    QueueType queue;
    int element;

    init_queue(&queue);
    printf("--데이터 추가 단계--\n");
    while(!is_full(&queue))
    {
        printf("정수를 입력하세요");
        scanf("%d", &element);
        enqueue(&queue, element);
        queue_print(&queue);
    }
    printf("큐는 포화상태입니다 \n\n");

    printf("--데이터 삭제 단계--\n");

    while(!is_empty(&queue))
    {
        element = dequeue(&queue);
        printf("꺼내진 정수 : %d \n", element);
        queue_print(&queue);
    }

    printf("큐는 공백상태 입니다 \n");
    return 0;



    
}

출력 결과

--데이터 추가 단계--
정수를 입력하세요1
QUEUE(front = 0 rear = 1)1 | 
정수를 입력하세요2
QUEUE(front = 0 rear = 2)1 | 2 | 
정수를 입력하세요3
QUEUE(front = 0 rear = 3)1 | 2 | 3 | 
정수를 입력하세요4
QUEUE(front = 0 rear = 4)1 | 2 | 3 | 4 | 
큐는 포화상태입니다 

--데이터 삭제 단계--
꺼내진 정수 : 1 
QUEUE(front = 1 rear = 4)2 | 3 | 4 | 
꺼내진 정수 : 2 
QUEUE(front = 2 rear = 4)3 | 4 | 
꺼내진 정수 : 3 
QUEUE(front = 3 rear = 4)4 | 
꺼내진 정수 : 4 
QUEUE(front = 4 rear = 4)
큐는 공백상태 입니다

*원형큐에서 front는 항상 큐의 첫번째 요소의 하나 앞을, rear은 마지막 요소를 가리킨다.