4. 큐(Queue)

▣ 큐(Queue)

■ 큐는 지난 포스팅에서 다루었던 스택(Stack)과 반대로 선입선출(FIFO : First-In First-Out)의 특징을 가지는 자료구조입니다.  가장 먼저 삽입(enqueue)된 데이터가 가장 먼저 삭제(dequeue)되는 구조를 가집니다.

 

■ 쉬운 예를 들어보자면, 식료품 상점에서 재고를 정리하는 것을 상상해보시면 됩니다. 각 상품에는 유통기한이 있고, 때문에 먼저 창고에 들어온 물건을 먼저(앞에) 진열 해야 합니다. 먼저 진열된 물건은 소비자에 의해 먼저 소비될 것입니다. 큐 또한 이와 마찬가지로 먼저 큐에 들어온 자료(data)가 먼저 삭제됩니다.

 

 ■ 스택에서 자료의 추가와 삭제가 스택의 top에서만 이루어졌던 것과 대조적으로, 큐에서는 자료의 추가와 삭제가 양방향에서 이루어집니다. 자료의 추가(enqueue)가 이루어지는 곳을 Rear(뒤), 자료의 삭제가 이루어지는 곳을 Front(앞)이라고 합니다.

큐(Queue)를 표현한 그림

 

큐를 구현하기 위한 두 가지 방법이 있습니다.

1. 선형 큐(linear queue) : 배열을 선형으로 사용하여 큐를 구현

2. 원형 큐(circular queue) : 배열을 원형으로 사용하여 큐를 구현

 

▣ 선형 큐

 아래 그림에서 보듯 선형 큐는 1차원 직선 형태의 배열로 구현된 큐입니다. 

 그림에서 현재 큐에는 5개의 data가 저장되어 있고, 두 개의 공간이 비어 있는 상태입니다. 위에서 설명드렸듯이 data의 삽입(추가)은 큐의 Rear에서만 이루어진다고 했습니다. 현재 상태에서 Rear에 자료를 추가하게 된다면 어떻게 될까요? 현재 저장되어 있는 data를 전부 한 칸씩 앞으로 옮겨 자리를 만들고, 6번 자리에 새로운 data를 추가해야 합니다. 아래 그림처럼 말이죠.

 이처럼 선형큐는 자료를 삽입할 때마다 모든 원소들을 한 칸씩 앞으로 옮겨야 한다는 치명적인 단점이 존재합니다. 이러한 작업은 O(n)의 시간복잡도를 가지는데, 큐의 크기가 작을 때에는 별로 중요하지 않지만 큐의 크기가 커지게 되면 그에 따라 데이터를 삽입하는데 걸리는 시간도 증가합니다. 또한 선형 큐에서 삽입과 삭제를 반복하다보면 큐가 실제로는 비어있음에도 컴퓨터가 큐의 요소가 가득 찼다고 생각하게 되는 case가 존재합니다. 이러한 단점으로 인해 선형 큐는 거의 사용되지 않습니다.

 

▣ 원형 큐

 선형 큐의 모든 단점을 커버하면서도 동일하게 동작하는 큐를 구현할 수 있습니다. 그것이 바로 원형 큐(circular queue)입니다. 원형 큐는 삽입시 data들을 이동할 필요가 없어 더 적은 연산으로 큐를 구현할 수 있습니다.

그림 출처 : C언어로 쉽게 풀어쓴 자료구조, 생능출판사

 원형 큐도 Front와 Rear의 위치(큐의 index)를 나타내기 위한 두 개의 변수를 가집니다. 위의  그림에서 A와 B라는 두 개의 데이터가 삽입 되어 있습니다. 그리고 Front는 0에 위치해 있고, Rear는 2에 위치해 있습니다. Front는 항상 큐의 첫 번째 데이터(큐에 남아있는 데이터들 중 가장 먼저 삽입 된 데이터)의 위치 한 칸 앞을 가리키며, rear는 항상 마지막 데이터의 위치를 가리킵니다. 

 

* 여기서 Front 또는 Rear가 큐의 위치를 가리킨다는 의미는 포인터처럼 주소를 가리킨다는게 아니고, Front와 Rear에 해당하는 큐의 index값을 변수로 저장하고 있다는 뜻입니다.

그림 출처 : C언어로 쉽게 풀어쓴 자료구조, 생능출판사

 위 그림은 큐의 데이터가 삽입되고 삭제되는 과정을 표현한 그림입니다. 초기에는 Read와 Front가 동일한 위치를 가리키고 있습니다. 그러다가 배열에 요소(element, data와 같은 뜻으로 사용)가 추가되면 Rear는 마지막으로 추가된 배열의 요소를 가리키게 됩니다. 앞서 큐에서 데이터의 삭제는 Front에서 이루어진다고 했으므로 삭제연산을 하면 Front가 가리키고 있는 위치에서 한 칸 뒤로 이동한 뒤에 해당 위치에 있는 요소를 삭제합니다. 

 

 여기까지 잘 따라오신 분들은 한 가지 의문점을 가지실 수 있습니다. 왜 큐에서 Front는 가장 먼저 삽입된 데이터의 위치를 가리키는 것이 아닌, 그 한 칸 앞을 가리킬까요? 그 이유는 원형 큐가 Front와 Rear의 위치를 통해 공백(empty), 포화(full), 오류(error) 상태를 나타내기 때문입니다.

그림 출처 : C언어로 쉽게 풀어쓴 자료구조, 생능출판사

 만약 위 그림의 (a)처럼 큐가 공백상태라면, Front와 Rear가 같은 index를 가리키게 됩니다. 그리고 큐가 위 그림 (b)처럼 포화상태라면, Front가 가리키는 위치는 (Rear + 1) % M이 됩니다.(여기서 M은 큐의 크기입니다.)

 그리고 (c)는 오류 상태인데, 앞서 공백상태에서 Front와 Rear가 같은 index를 가리킨다고 설명했는데, (c)와 같이 되면 큐가 가득 찼는데도 Front와 Rear가 같은 index를 가리키게 되어 이를 공백상태로 봐야할지, 큐가 가득 찬 상태로 봐야할지 애매하게 됩니다. 따라서 선형 큐를 구현할 때는 (b)와 같이 항상 하나의 요소가 저장될 공간을 비워둬야 합니다.

 

 아직 Front가 왜 가장 먼저 삽입된 요소의 위치 한 칸 앞을 가리키는지 설명드리지 않는 것 같네요. 그 이유는 큐의 공백 상태를 표현하는 것과 관련 있습니다. 만약 Front가 가장 먼저 삽입된 요소의 위치를 가리키게 된다면, 공백 상태에서 요소가 하나 추가되었을 때, Front와 Rear가 같은 index를 가리키게 됩니다. 따라서 이 경우, 공백 상태가 아님에도 큐를 공백상태라고 인지하게 됩니다. 두 번째 요소가 추가 되었을 때는 Front와 Rear가 가리키는 index가 달라지지만, 삭제(dequeue)가 발생하면 다시 Front와 Rear가 같은 index를 가리키게 되어 공백상태로 인지하게 됩니다. 

 

 이제 큐를 프로그램으로 구현해볼 시간인 것 같습니다. 대충 필요한 함수(연산)이 뭐가 있을지 생각해보면, 큐가 가득 찼는지 체크하는 함수, 큐가 비어있는지 체크하는 함수, 큐에 요소를 삽입하는 함수, 큐에서 요소를 제거하는 함수 정도가 필요할 것 같습니다. 

// queue.h
 
#define MAX_QUEUE_SIZE 10
 
typedef int element;
 
typedef struct {
    element data[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;
 
void init_queue(QueueType* q);
 
int is_empty(QueueType* q);
 
int is_full(QueueType* q);
 
void enqueue(QueueType* q, element item);
 
element dequeue(QueueType* q);
 
extern QueueType queue;
extern QueueType* q;
 

 

// queue.c
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
 
QueueType queue;
QueueType* q = &queue;
 
 
void init_queue(QueueType* q) {
    printf("init queue...\n");
    q->front = 0;
    q->rear = 0;
}
 
int is_empty(QueueType* q) {
    return q->front == q->rear;
}
 
int is_full(QueueType* q) {
    return q->front == (q->rear + 1) % MAX_QUEUE_SIZE;
}
void enqueue(QueueType* q, element item)
{
    if (is_full(q)) {
        fprintf(stderr, "ERROR : Queue is full");
        exit(1);
    }
 
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}
 
element dequeue(QueueType* q) {
    if (is_empty(q)) {
        fprintf(stderr, "ERROR : Queue is empty");
        exit(1);
    }
 
    q->front = (q->front + 1) % MAX_QUEUE_SIZE; // front를 증가시키고
    return q->data[q->front]; // 그 후에 데이터 반환
}
 
 

// main.c
 
#include "queue.h"
#include <stdio.h>
 
int main() {
 
    init_queue(q);
    printf("# of front : %d, # of rear : %d\n", q->front, q->rear);
 
    enqueue(q, 3);
    printf("enque : %d, # of front : %d, # of rear : %d\n", q->data[q->front+1], q->front, q->rear);
 
    enqueue(q, 4);
    printf("enque : %d, # of front : %d, # of rear : %d\n", q->data[q->front+2], q->front, q->rear);
    enqueue(q, 5);
    printf("enque : %d, # of front : %d, # of rear : %d\n", q->data[q->front+3], q->front, q->rear);
 
    printf("dequeue : %d, ", dequeue(q));
    printf("# of front : %d, # of rear : %d\n", q->front, q->rear);
    printf("dequeue : %d, ", dequeue(q));
    printf("# of front : %d, # of rear : %d\n", q->front, q->rear);
    printf("dequeue : %d, ", dequeue(q));
    printf("# of front : %d, # of rear : %d\n", q->front, q->rear);
 
    dequeue(q);
 
    return 0;    
}

 확실히 함수와 구조체 등을 따로 선언하고 정의하니 main함수가 깔끔해지는군요. 큐를 초기화 한 다음 enqueue()를 통해 3개의 요소를 삽입하고 다시 3번의 dequeue()를 통해 추가된 요소들을 삭제했습니다. 그리고 에러메세지가 제대로 발생되는지 확인하기 위해 한 번 더 dequeue()를 호출했습니다.

 

 결과를 확인해보니 FIFO로 제대로 큐가 동작하는 것 같습니다.

 

■ 큐와 비슷한 구조를 가지는 덱(Deque)이라는 자료구조도 있습니다. Deque은 double-ended queue의 준말인데, 큐가 요소의 삽입은 Rear에서, 요소의 삭제는 Front에서 이루어지던 것과 달리 덱은 front와 rear 양 쪽에서 삽입과 삭제가 모두 가능합니다. 즉, front에서 삭제와 삽입을 할 수 있고, rear에서 삽입과 삭제를 할 수 있습니다. 하지만 잘 사용되지는 자료 구조이므로 그냥 이런 것도 있다는 정도로만 알아두시면 될 것 같습니다. 추후에 여유가 되면 덱에 대해서도 다뤄보겠습니다.

 

[참고자료]

1. 생능출판사, C언어로 쉽게 풀어쓴 자료구조