[자료구조]큐(Queue) - 배열

큐는 입구와 출구가 따로 있는 긴 통이라고 생각하면 된다. 큐는 접근이 제한된 자료구조이며 행위적 측면을 부여받은 추상적 자료형이기 때문에 큐를 조작하는 방법은 두가지로 제한되어 있다. 

큐를 조작하는 방법은 put 동작과 get 동작이 있다. 큐에 자료를 집어넣을 때는 뒤(rear)에서 집어넣는다. 이 집어넣는 동작은 put 동작이라고 한다. 그리고 큐에서 자료를 얻어낼 때는 앞(front)에서 얻어낸다. 이 자료를 얻는 동작은 get 동작이라고 한다. 

배열을 이용해서 큐를 구현하는 것은 문제가 없어 보이지만 문제가 많다. 배열을 이용한 큐의 구현은 자료를 저장할 배열과 앞과 뒤를 가리키는 변수만 있으면 될 것같다. 

하지만 큐에 자료를 집어 넣고 빼는 동작을 계속하다보면 rear와 front는 계속 증가되기만 한다. 결국에는 큐는 전체적으로 배열 속을 이동하게 되며 이 경우 실제로 저장하고 있는 자료는 몇개되지 않지만 rear가 배열의 한계를 넘어서서 오버플로 에러를 발생할 수 있다. 오버플로를 방지하기 위해서 rear가 배열에 끝에 이르렀는지를 점검해서 배열에 끝에 닿았을 경우 큐의 내용 전체를 복사해서 배열의 앞부분으로 옭기는 동작이 필요하다. 

이 점이 배별을 이용하여 큐를 구현할 때의 문제점이다. 해결 방법은 원형 큐를 이용하는 것이다. 원형 큐는 배열의 첫 요소와 마지막 요소가 붙어서 마치 뱀의 머리가 꼬리를 물고 있는 듯한 모양이다. 원형 큐는 간단하게 제일 처음 요소의 앞 요소는 제일 마지막 요소이고, 제일 마지막 요소의 뒷 요소는 제일 앞 요소라는 조작에 의해서 가능해진다. 긜고 이 조작은 나머지 연선(% 연산)을 이용하여 간단하게 구현된다. 

하지만 원형큐에서 주의해야 할 부분이 있다. front와 rear가 같은 경우 rear가 값이 채우고 front와 만난것인지 값이 없어서 front와 만난것인지 알 수가 없다. 이 문제는 간단하게 배열의 크기를 전부 사용하지 않고 배열의 크기를 하나적게 사용하면 된다. 

#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 Overfolw");
        return -1;
    }
 
    queue[rear] = k;
    rear = ++rear % MAX;
    return k;
}
 
// 출력
int get(void){
    int i;
    if (front == rear){
        printf("\n Underfolw");
        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]);
    }
}
 
 
// Main
void main(void){
    int i;
    init_queue();
 
    printf("\n 5, 4, 7, 8, 2, 1");
    put(5);
    put(4);
    put(7);
    put(8);
    put(2);
    put(1);
    print_queue();
 
    printf("\n Get");
    i = get();
    print_queue();
 
 
}