[C언어와 함께 자료구조를] 큐(Queue)의 개념, 배열로 큐 구현하기

큐의 개념

큐는 스택과 비슷한 모양을 하고 있지만, 조작방식은 다릅니다. 큐의 구조도 간단한데,스택과 달리 앞 뒤가 뚫린 통이라고 보시면 됩니다. 이 통은 뒤에서 뭔가를 집어넣고 앞에서 빼냅니다. 즉, 먼저 들어온 것은 먼저 나오는 구조로 FIFO(First In First Out)이라고 부릅니다.

큐(Queue)의 기본 개념

큐의 연산은 put과 get이 있습니다. 큐에 자료를 집어 넣을 때는 뒤(rear)에서 처리하고, 이를 put 이라고 합니다. 반대로 큐에서 자료를 빼낼 때는 앞(front)에서 처리하고 이를 get이라고 합니다. 그림을 보시면 쉽게 이해하시겠죠?

배열로 큐 구현하기

배열을 이용한 큐의 구현은 스택의 구현과 비슷한 난이도일 것 같지만, 조금 더 생각해보면 문제가 아주 많습니다. 먼저 저장할 자료의 앞과 뒤를 가리키는 변수를 선언하여 큐의 구조를 정의해 보겠습니다.

#define MAXSIZE 10   // 큐의 크기

int queue[MAXSIZE];

int front=-1, rear=-1;

다음으로 put과 get 연산을 정의해 보겠습니다.

int put (unsigned int val) { 

    if (rear >= MAXSIZE-1) {

        printf (" Queue Overflow");

        return (-1);

    }

    queue[++rear] = val;

} 

   

int get () {

   if (front <= 0) {

        printf (" Queue Underflow");

        return -1;

   }

   return queue[front++];

}

자...이렇게 연산을 정의 하면 될까요? 배열의 인덱스로 사용되는 front와 rear가 위 코드에서는 계속 증가하기만 합니다. 결국 몇번의 연산을 한 후에 rear가 배열의 한계를 넘어 더이상 put연산이 Overflow에러를 발생시킬 수 있습니다. 그러므로 rear가 배열의 한계에 다다랐을 때에 큐의 데이터를 배열의 앞부분으로 옮기는 동작이 필요하게 됩니다.

int put (unsigned int val) { 

    if (rear >= MAXSIZE-1) {

		if (!(rear-front)) {
            return -1;
        }

        /* 여기서 배열의 앞으로 옮겨야 한다. */
        memcpy (&queue[0], &queue[front], rear-front+1);
        rear=rear-front;
        front = 0;
    }
    queue[++rear] = val;
} 

 

지금은 배열의 개수를 10으로 정의 했지만 만약에 5억개라면? 그런 데이터 이동이 put할때마다 발생한다면? 당연히 비효율적이겠죠.

그래서 해결방법으로 나왔습니다. 환형 (또는 원형) 큐(Circular Queue)를 이용하는 것입니다. 환형 큐는 뱀이 꼬리를 물고 있는 듯한 모양을 가지고 있습니다. 데이터가 순환하며 저장되기 때문에 끝이라는 개념도 없습니다. 다음 그림을 보시죠.

환형 큐(Circular Queue)

 

어? 처음의 개념도에서는 rear가 큐의 끝을 가리키고 있었는데, 여기서는 그 다음 빈 공간을 가리키고 있네요. 이상한가요?

만약 rear가 Queue의 끝을 가리킨다면, 큐가 비어 있는 경우를 어떻게 나타내야 할까요? front와 rear가 같은 경우라고 생각할 지 모르겠지만, front와 rear가 같다는 것은 큐에 데이터가 하나 들어 있다는 의미를 나타내게 됩니다. 따라서 rear가 큐의 끝 다음 빈 공간을 가리키게 되면 front와 rear가 같은 경우 큐가 비어 있는 상태가 됩니다. 이 환형큐 모델에서는 큐의 마지막 공간을 하나 비워 놓음으로서(데이터를 저장하지 않는 공간) 큐가 꽉차 있는 경우와 큐가 비어있는 경우(front == rear)가 충돌하지 않도록 해 줍니다.

그러면, 환형 큐를 초기화하는 함수와 큐를 비우는 함수를 만들겠습니다.

void init_queue (void) { 
   front = rear = 0;
} 

void clear_queue (void) {
   front = rear;
}

앞서 환형 큐는 끝이 없는 큐의 개념이므로 0부터 MAXSIZE-1까지의 배열 인덱스를 순차적으로 증가시켜 사용하지 않고, %연산을 통해 빈공간에 쓰거나(put) 데이터를 가져오게(get) 됩니다.

int put(int val) { 

    if ((rear+1) % MAXSIZE == front) {    // 큐가 꽉 찼는지 확인
        printf ("    Queue Overflow.");
        return -1;
    }

    queue[rear] = val;                         // rear가 큐의 끝 다음의 빈공간이므로 바로 저장
    rear = ++ rear % MAXSIZE;             // rear를 다음 빈공간으로 변경

	return val;
} 

   

int get (void) {
    int i;

    if (front == rear) {    // 큐가 비어 있는지 확인
        printf ("    Queue Underflow.");
        return (-1);
    }

    i = queue[front];    // front의 값을 가져옴
    front = ++front%MAXSIZE;   // front를 다음 데이터 요소로

    return i;
}

환형 큐에서는 저장소의 크기보다 하나 작은 개수의 데이터를 저장할 수 있다는 것과, 무한 순환되므로 %연산을 이용하여 배열에 저장해야 된다는 것을 기억한다면 구현은 별로 어렵지 않습니다.

(참고로 %연산은 나머지 연산이므로 MAXSIZE로 나눈 나머지는 0~MAXSIZE-1개가 됩니다. 순차적으로 front와 rear가 증가하므로 MAXSIZE의 나머지만큼 순차적으로 돌아가며 사용하게 됩니다.)

#include <stdio.h>

#define MAXSIZE 10   // 큐의 크기

int queue[MAXSIZE];
int front, rear;

void init_queue (void) { 
   front = rear = 0;
}

void clear_queue (void) {
   front = rear;

}

int put(int val) {

    if ((rear+1) % MAXSIZE == front) {    // 큐가 꽉 찼는지 확인
        printf ("    Queue Overflow.");
        return -1;
    }

    queue[rear] = val;                    // rear가 큐의 끝 다음의 빈공간이므로 바로 저장
    rear = ++ rear % MAXSIZE;             // rear를 다음 빈공간으로 변경
    return val;
} 

int get (void) {
    int i;

    if (front == rear) {                  // 큐가 비어 있는지 확인
        printf ("    Queue Underflow.");
        return (-1);
    }

    i = queue[front];    // front의 값을 가져옴
    front = ++front%MAXSIZE;   // front를 다음 데이터 요소로
    return i;
}
  
void print_queue (void) {
        int i;
    printf (" Queue From Front------> To Rear ");
    for (i = front; i != rear; i = ++i%MAXSIZE)
        printf("%-6d", queue[i]);
}

void main(void)
{
    int i;

    init_queue ();

    printf (" Put 5, 4, 7, 8, 2, 1");
    put(5);
    put(4);
    put(7);
    put(8);
    put(2);
    put(1);
    print_queue(); 

    printf(" Get");
    i = get();
    print_queue();
    printf("    get value is %d", i);

    printf(" Put 3, 2, 5, 7");
    put(3);
    put(2);
    put(5);
    put(7);
    print_queue();   

    printf(" Now queue is full, put 3");
    put(3);
    print_queue(); 

    printf(" Initialize Queue");
    clear_queue();
    print_queue();  

    printf(" Now queue is empty, get");
    i = get();
    print_queue();
    printf("    get value is %d", i);
}

PS C:\CS> .\queue

Put 5, 4, 7, 8, 2, 1
 Queue From Front------> To Rear
5     4     7     8     2     1     
Get
 Queue From Front------> To Rear
4     7     8     2     1     
   get value is 5
Put 3, 2, 5, 7
 Queue From Front------> To Rear
4     7     8     2     1     3     2     5     7     
Now queue is full, put 3
   Queue Overflow.
 Queue From Front------> To Rear
4     7     8     2     1     3     2     5     7     
Initialize Queue
 Queue From Front------> To Rear

Now queue is empty, get
   Queue Underflow.
 Queue From Front------> To Rear

   get value is -1

다음시간에는 연결리스트 (Linked List)에 대해서 공부해 보고, 이어서 연결리스트로 스택과 큐를 구현해 보도록 하겠습니다.