[자료구조론] C로 큐를 만들자

안녕하세요. 김용성입니다.
오늘은 저번에 했던 스택 포스팅과 마찬가지로 자료구조 중 큐(Queue)에 대해 알아보는 시간을 가져보도록 하겠습니다.

이번 포스팅은 c언어에 대한 어느정도 기본 지식이 있는 컴퓨터공학 전공 1,2학년 혹은 비전공자 분들에게 많은 도움이 되실 거라 생각해요.

큐

스택의 경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐는 먼저 들어온 데이터가 먼저 나가는 구조입니다.

즉 FIFO: First-In First-Out 선입선출 형태를 띱니다. 그림으로 보여드리도록 할께요.

스택과는 모양이 조금 다르고 용어도 다르며 메소드의 이름도 다릅니다.
스택에 push와 pop이 있었다면 큐에는 enqueue와 dequeue라는 것이 있어요. 여기서 혼동해서는 안되는 것은 데이터는 큐의 후단(rear)에 삽입되고 전단(front)를 통해 나간다는 점입니다.
저는 조금 머리가 나빠서 그런지 가끔 큐 구현 코드를 작성하다가 변수명을 거꾸로해서 만들 때가 간혹 있더라구요..

추상 자료형 큐

코드로 작성하기 전 큐의 메소드를 추상화하여 정의해보도록 하겠습니다.

create(max_size)
최대 크기가 max_size인 공백큐 생성
init(q)
큐 초기화
is_full(q)
if(큐의 원소 수==size) return TRUE;
else return FALSE;
is_empty(q)
if(큐의 원소 수==0) return TRUE;
else return FALSE;
enqueue(q,item)
if(is_full(q)) return OVERFLOW_ERROR;
else 큐의 후단에 item 추가;
dequeue(q)
if(is_empty(q)) return UNDERFLOW_ERROR;
else 큐의 전단 item 제거하여 반환;
peek(q)
if(is_empty(q)) return UNDERFLOW_ERROR;
else 큐의 전단 item 제거없이 반환만;

이런식으로 큐의 메소드들을 구현할 수 있습니다.

스택과 상당히 유사하지만, 스택은 상단에서만 데이터의 입출입이 일어나는 반면 큐는 전단과 후단 양쪽에서 각각 데이터의 출입 기능을 수행하죠. front와 rear에 대해 잘 기억하셔야 합니다.

queue 코드 (linear queue)

제가 위에서 설명드린 큐는 기본적으로 큐의 모양이 선형이라고 가정한 채 만든 것입니다. 이것을 Linear Queue, 즉 선형큐라고 부르죠. 가장 간단하게 사용되는 방식인만큼 구현하기도 어렵지 않죠.

큐의 핵심은 초기값에 있습니다. 스택에서 초기의 top값을 -1으로 설정했던 것처럼, 선형 큐도 마찬가지로 front와 rear의 초기 값을 -1이라고 해줍니다. 데이터가 0번 index부터 저장되기 때문이라고 설명드렸었죠?

데이터가 증가(enqueue)할 경우에는 rear값을 증가시키고 그 위치에 데이터를 저장합니다. 그리고 데이터를 삭제(dequeue)할 때에는 front를 하나 증가시키고 front가 가리키는 위치에 있는 데이터를 삭제하여 반환하죠.

그렇다면 공백 상태는 어떻게 될까요??

선형 큐에서의 공백 상태는 front값과 rear값이 같아진 상태입니다. 데이터가 삭제되면 front값이 증가하면서 점차 rear값과 가까워지겠죠?? rear값이 -1인 상태라고 착각하실 수 있는데 이것은 혼돈해서는 안됩니다!

이제 C언어를 통해 선형 큐를 구현해보겠습니다.

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

#define MAX_QUEUE_SIZE 5
#define MAX_STRING 100

typedef struct{ // 학생 구조체 생성
    int student_number;
    char student_name[MAX_STRING];
    char student_address[MAX_STRING];
}student;

typedef struct{
    int front;
    int rear;
    student data[MAX_QUEUE_SIZE];
} Queue;

void init_queue(Queue *q){
    q->front=q->rear=-1;
}

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

int is_full(Queue *q){
    return q->rear==MAX_QUEUE_SIZE-1;
}

int is_empty(Queue *q){
    return q->rear==q->front; // 공백상태 
}

void enqueue(Queue *q,student object){
    if(is_full(q)){
        error("OVERFLOW");
        return;
    }
    q->data[++q->rear]=object;  //rear값을 증가시킨 후 반환
}

student dequeue(Queue *q){
    if(is_empty(q)){
        error("UNDERFLOW");
    }
    return q->data[++q->front]; //front값을 증가시킨 후 반환
}

student peek(Queue *q){
    if(is_empty(q)){
        error("UNDERFLOW");
    }
    int index=q->front+1; // front값을 변화시키지 않기 위해 별도 변수 선언
    return q->data[index];
}


int main() {

     student object={201511796,"kys","Seoul"}    ;

     Queue q;
     init_queue(&q);

     enqueue(&q,object);

     student s=dequeue(&q);

     printf("student number:%d\n",s.student_number);
     printf("student name:%s\n",s.student_name);
     printf("student address:%s\n",s.student_address);

}

student number:201511796
student name:kys
student address:Seoul

이런 식으로 구현할 수가 있어요. 이러한 선형 큐는 CPU의 작업 스케줄링에서도 사용됩니다. 큐를 사용하여 우선순위를 결정해주는 것이죠.
그러나 이러한 선형 큐에는 분명한 문제점이 존재하는데요. 그것은 바로 front와 rear값이 계속해서 증가만 하기 때문에 배열의 앞부분이 비어있더라도 사용하지 못한다는 점입니다. 이러한 작업을 가능하게 하기 위해서는 주기적으로 모든 요소들을 후단으로부터 전단으로 이동시켜야 하는데 매번 이동시키면 코드의 수행시간도 잡아먹게 되고, 코드 또한 복잡해지겠죠?

그런 이유로 인해 원형 큐라는 것을 고안해내었고, 원형 큐는 선형 큐보다 훨씬 효율적으로 동작합니다. 이번에는 원형 큐를 한번 구현해보도록 하겠습니다.

queue 코드 (circular queue)

원형 큐는 큐를 선형으로 생각하지 않고 원형으로 생각함으로써 rear의 값이 MAX_SIZE-1에 도달하게 될 경우(선형 큐에서는 이 상태를 포화상태라고 하죠.) 그 다음의 rear 값이 0이 되도록 하는 것입니다. 개념상으로 원형으로 배열의 인덱스를 변화시켜준다고 생각하시면 됩니다!

원형 큐를 구현할 때의 중요한 개념 3가지가 있습니다.

• %연산자를 활용하기
• 원형큐의 경우 꼭 한칸이 비어있어야 한다.(공백상태, (MAX_SIZE가 8일 경우에는 7개의 데이터 저장 가능)
• 원형 큐의 공백 상태는 front==rear / 포화 상태는 front가 rear보다 하나 앞에 있는 경우
  원형 큐를 코드로 구현할 때 가장 핵심은 %연산자를 활용한다는 것입니다. %연산자를 활용하여 큐의 MAX_SIZE를 넘지 않게끔 유지하는 것이 중요하죠. 다음의 추상화 메소드들을 보시면 이해되실 겁니다.

enqueue(q,x)
rear<-(rear+1)%MAX_SIZE; // MAX_SIZE로 나누어준 나머지를 구해 할당
q[rear]<-x;
dequeue(q)
front<-(front+1)%MAX_SIZE;
return q[front];

공백상태와 포화상태는 다음과 같이 판별합니다.

is_empty(q)
return rear==front;
is_full(q)
return (rear+1)%MAX_SIZE=front;

이제 코드를 작성해보도록 하겠습니다.

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

#define MAX_QUEUE_SIZE 5

typedef int element;

typedef struct{
    int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
} CircularQueue;


void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

void init_queue(CircularQueue *q){
    q->rear=q->front=0;
}

int is_full(CircularQueue *q){
    return (q->rear+1)%MAX_QUEUE_SIZE==q->front; // front값이 rear값보다 하나 앞서는 경우
}

int is_empty(CircularQueue *q){
    return q->rear==(q->front); //front값과 rear값이 같은 경우
}

void enqueue(CircularQueue *q,element item){
    if(is_full(q)){
        error("OVERFLOW");
        return ;
    }
    q->rear=(q->rear+1)%MAX_QUEUE_SIZE;
    q->data[q->rear]=item;
}

int dequeue(CircularQueue *q){
    if(is_empty(q)){
        error("UNDERFLOW");
    }
    q->front+=1;
    return q->data[(q->front)&MAX_QUEUE_SIZE];
}

void print_queue(CircularQueue *q){

    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->rear);
    }
    printf("\n");
}


int main() {
   CircularQueue queue;
   element number;
   init_queue(&queue);
   printf("--enqueue--\n");
   while(!is_full(&queue)){
       printf("insert number:");
       scanf("%d",&number);
       enqueue(&queue,number);
       print_queue(&queue);
   }
   printf("queue is full\n");
   printf("--dequeue--\n");
   while(!is_empty(&queue)){
        number=dequeue(&queue);
        printf("out number:%d\n",number);
        print_queue(&queue);
   }
   printf("queue is full\n");
   return 0;
}

다음과 같이 출력되는 것을 확인하실 수 있습니다!

--enqueue--
insert number:10
10 |
insert number:20
10 | 20 |
insert number:30
10 | 20 | 30 |
insert number:40
10 | 20 | 30 | 40 |
queue is full
--dequeue--
out number:10
20 | 30 | 40 |
out number:-858993460
30 | 40 |
out number:10
40 |
out number:40

dequeue 만들기

이제 마지막으로 deque라는 것을 만들어 보겠습니다.
dequeue는 double ended queue의 줄임말으로 front에서도 데이터 입력 출력이 가능하고 rear에서도 데이터 입출력이 가능한 queue를 일컫습니다. 그렇기에 새로운 메소드들이 등장하죠.
추상메소드들을 작성해보도록 하겠습니다.

create(max_size)
최대 크기가 max_size인 공백큐 생성
init(dq)
큐 초기화
is_full(dq)
if(큐의 원소 수==size) return TRUE;
else return FALSE;
is_empty(dq)
if(큐의 원소 수==0) return TRUE;
else return FALSE;
add_front(dq,e)
if(is_full(q)) return OVERFLOW_ERROR;
else 큐의 후단에 item 추가;
add_front(dq,e)
if(is_full(q)) return OVERFLOW_ERROR;
else 큐의 전단에 item 추가;
delete_front(dq)
if(is_full(q)) return OVERFLOW_ERROR;
else 큐의 전단 item 삭제 및 반환;
delete_rear(dq)
if(is_full(q)) return OVERFLOW_ERROR;
else 큐의 후단 item 삭제 및 반환
get_front(dq)
if(is_empty(q)) return UNDERFLOW_ERROR;
else 큐의 전단 item 제거없이 반환;
get_rear(dq)
if(is_empty(q)) return UNDERFLOW_ERROR;
else 큐의 전단 item 제거없이 반환만;

이것저것 메소드들이 많다고 걱정하실 필요 없습니다. 스택이나 기본 큐에서 다뤘던 메소드들과 크게 다를 것이 없기 때문이죠.
dequeue의 경우 원형큐와의 공통점이 많으므로 이와 비슷하게 구현할 수 있습니다. 그렇다는 것은 데이터가 회전한다고 가정을 해야겠죠?
다른 메소드는 원형큐와 상당히 유사하지만 delete_rear과 add_front에서는 원형큐와는 반대의 회전이 필요하기 때문에 아래의 로직은 이해를 해두어야 합니다.

front<-(front-1+MAX_SIZE)%MAX_SIZE // add_front시 front의 변화
rear<-(rear-1+MAX_SIZE)%MAX_SIZE // delete_rear시 rear의 변화

이제 코드를 구현해보도록 하겠습니다.

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

#define MAX_QUEUE_SIZE 5

typedef int element;

typedef struct{
    int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
} deQueue;

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

void init_queue(deQueue *dq){
    dq->rear=dq->front=0;
}

int is_full(deQueue *dq){
    return dq->front==(dq->rear+1)%MAX_QUEUE_SIZE;
}

int is_empty(deQueue *dq){
    return dq->front==dq->rear;
}

void deque_print(deQueue *dq){
    printf("DEQUE(front=%d rear=%d)=",dq->front,dq->rear);
    if(!is_empty(dq)){
        int i=dq->front;
        do{
            i=(i+1)%MAX_QUEUE_SIZE;
            printf("  %d  |",dq->data[i]);
            if(i==dq->rear)
                break;
        }while(i!=dq->front);
    }
    printf("\n");
}

void add_front(deQueue *dq,element item){
    if(is_full(dq)){
        error("OVERFLOW");
        return;
    }
    dq->data[dq->front]=item;
    dq->front=(dq->front-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE; //front 값 감소

}

void add_rear(deQueue *dq,element item){
    if(is_full(dq)){
        error("OVERFLOW");
        return;
    }
    dq->rear=(dq->rear+1)%MAX_QUEUE_SIZE;
    dq->data[dq->rear]=item;
}

element delete_front(deQueue *dq){
    if(is_empty(dq)){
        error("UNDERFLOW");
    }
    dq->front=(dq->front+1)%MAX_QUEUE_SIZE;
    return dq->data[dq->front];
}

element delete_rear(deQueue *dq){
    if(is_empty(dq)){
        error("UNDERFLOW");
    }
    element item=dq->data[dq->rear];
    dq->rear=(dq->rear-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE; //rear값 감소
    return item;
}

element get_front(deQueue *dq){
    if(is_empty(dq)){
        error("UNDERFLOW");
    }
    return dq->data[dq->front+1]%MAX_QUEUE_SIZE;
}

element get_rear(deQueue *dq){
    if(is_empty(dq)){
        error("UNDERFLOW");
    }
    return dq->data[dq->rear];
}

int main(void) {
    deQueue  queue;
    init_queue(&queue);
    for(int i=0;i<3;i++){
        add_front(&queue,i);
        deque_print(&queue);
    }
    for(int i=0;i<3;i++){
        delete_rear(&queue);
        deque_print(&queue);
    }

    return 0;

}

다음과 같은 출력 결과를 받을 수 있습니다.

DEQUE(front=4 rear=0)= 0 |
DEQUE(front=3 rear=0)= 1 | 0 |
DEQUE(front=2 rear=0)= 2 | 1 | 0 |
DEQUE(front=2 rear=4)= 2 | 1 |
DEQUE(front=2 rear=3)= 2 |
DEQUE(front=2 rear=2)=

원형 큐와 dequeue 코드를 작성할 때 좀 헷갈리는 부분이 있다면, 무조건 front와 rear의 요소가 늘어나거나 줄어드는 메소드를 구현할 때는 무조건 %MAX_SIZE라는 나머지 연산이 들어간다는 것만 알고있으면 됩니다. 그렇게 해야 배열의 index가 정해진 MAX_SIZE로부터 벗어나지 않기 때문이죠. 그렇게 생각을 한 뒤에 각각의 front와 rear이 커지는지 작아지는지에 대해 생각하고 코드를 구현하신다면 아마 잘못된 코드를 작성할일은 없으실 거라 생각합니다 :)

마무리

오늘 포스팅한 큐의 경우에는 컴퓨터 내부 버퍼에서 컴퓨터의 여러 입출력을 조율할때 주로 사용되며 여러분들이 훗날 코딩테스트에서 너비 우선 탐색(BFS 탐색 알고리즘이라고 합니다)에서도 이를 활용할 것입니다.

이런것 다 모듈로 사용할 수 있지 않나요? 파이썬에도 dequeue 모듈이 있던데요??

네 맞습니다. C++에도 Stack과 Queue,Dequeue 관련된 모듈이 존재해요. 그렇지만 자료구조를 응용하고 활용하기 위해서는 기본적으로 어떻게 돌아가는지 직접 코드를 통해 만들어보고 수행해보는 것이 좋다고 생각합니다.

큐라는 자료구조 모듈을 사용하기 전에 이런 개념적인 부분들을 잘 체크해보시는 건 어떨까요??

긴 글 읽어주셔서 감사합니다.