알고리즘 정리(C언어)

"알고리즘 정리(C언어) - 3. 큐" 목차

큐

큐는 은행에 가서 창구 대기번호표를 뽑는 것과 비슷하다. 먼저 온 사람이 먼저 일을 처리할 수 있다. 우리는 창구가 손님들로 가득 차 있더라도 번호표를 뽑는다. 왜냐하면 은행에서는 차례가 된 고객의 일을 진행하면서도 다음에 처리할 고객의 일들을 순번으로 대기시키는 알고리즘을 사용하기 때문이다. 이것이 바로 큐다.

이런 자료구조를 FIFO(First In-First Out)라고 한다. 한자어로는 선입선출先入先出이라고 부른다. 큐는 시스템에 과부하가 걸리지 않게 해주는 완충장치 역할을 한다.

사용 예시로는 서로 다른 프로세스, 쓰레드 혹은 서버 간에 데이터를 주고받는 경우 사용하는 버퍼 등을 들 수 있다.

큐의 필수 ADT 역시 간단하다. 삽입Enqueue과 제거Dequeue만 있으면 된다. 스택과 달리 삽입은 후단Rear에서, 제거는 전단Front에서만 진행한다.

배열 기반 큐(순환 큐)

순환 큐Circular Queue란, 원형 큐나 링 버퍼Ring buffer로 불리기도 한다. 순환 큐는 배열 기반의 큐를 만들려다가 자연스럽게 나온 형태의 큐라고 생각하면 이해하기 좋다. 차근차근 논리구조를 따라가면 구현 형태가 자연스럽다. 굳이 특징을 외워서 기억하려 할 필요가 없다.

배열로 큐를 만든다고 생각해보자. 우선 capacity를 지정한다. 앞단(다음에 시작할 작업이 있는 공간을 가리키는 포인터pointer다)의 인덱스index는 0으로 고정한다. 새로운 요소는 후단(새로운 요소가 들어올 공간을 가리키는 pointer)에 채워넣는다. 요소를 제거할 때에는 배열 맨 앞 요소를 제거하고, 나머지 모든 요소의 인덱스를 1씩 빼준다.

하지만 배열을 잘 아는 사람이라면, 혹은 C언어의 배열에 대해 깊이 살펴본 사람이라면 이 연산에 엄청난 에너지가 들어간다는 것을 알 수 있다. 배열은 단순하게 도식화하면 '같은 길이의 주소를 가진 요소들의 연속된 유한한 주소 공간'이다. 즉, 인덱스를 1씩 빼준다는 것은 모든 배열의 요소가 가리키고 있는 주소값을 전부 변경해주어야 한다는 것이다. O(N)의 연산이 필요하므로 속도가 느릴 수밖에 없다.

이 문제의 해결을 위해 배열의 요소들은 그대로 두고, 제거 시에 전단의 인덱스 값을 변경(즉, 1 추가)하도록 구현할 수 있다. 그러면 전단의 인덱스 값만 변경하면 되기 때문에 O(1)의 연산이 필요하다. 새로운 요소도 후단에 추가하며 인덱스 값을 늘려가면 되므로 매우 빠르다. 좋다. 하지만 이 방법에도 단점이 있는데 전단에서 요소가 빠져나가고, 후단에 요소가 추가될수록 배열의 용량capacity이 줄어든다는 것이다.

그러면 어떻게 하면 될까? 100개의 작업이 대기할 수 있는 큐를 만들었다고 치자. 전단에서 계속 작업이 빠져나가고 후단에 새로운 작업이 쌓이다보면 언젠가는 후단의 인덱스 값이 99가 되는 때가 온다(인덱스는 0부터 센다). 그러면 그때 전단에서 데이터가 빠져나가고 빈 자리를 후단의 인덱스 값을 이동시켜 사용하면 되지 않을까? 즉 대기번호가 99까지 차면 다음 고객에게는 대기번호 0번을 주는 것이다. 왜냐하면 이미 0번 대기번호를 가진 고객은 일을 처리하고 나갔으므로 번호가 겹치는 작업이 남아있지 않기 때문이다.

좋다. 하지만 이 방법에도 문제가 있다. 전체 큐에 아무 고객이 없거나, 전체 큐가 고객으로 꽉 차서 포화상태가 된 경우, 전단과 후단의 인덱스 값이 동일하다(전단은 다음 번에 나갈 데이터를 가리키고 후단은 다음 번에 들어올 데이터가 앉을 자리를 미리 가리키고 있기 때문이다). 때문에 전체 큐에 고객이 꽉찬 상태와 텅텅 빈 상태를 구분하기가 어렵다.

이를 해결하기 위해서 도입한 것이 하나의 더미 노드dummy node다. 더미 노드를 둠으로써 전체 큐가 빈 상태에서는 전단과 후단의 인덱스 값이 동일하게 되지만, 전체 큐에 고객이 꽉 찬 상태에서는 인덱스가 달라지게 된다. 후단은 마지막 남은 더미 노드를 가리키고 있게 된다.

이것이 순환 큐의 전말이다. 이 시나리오를 기억하고 있다면 순환 큐의 특징을 기억하는 것은 물론 구현하는 데에 있어서도 덜 어려움을 겪게 된다.

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

typedef int ElementType;

typedef struct _CQNode
{
    ElementType Data;
} CQNode;

typedef struct _CQ
{
    int Capacity;
    int Front;
    int Rear;

    CQNode* CQNodes;
} CQ;

void CreateCQ( CQ** Queue, int cap )
{
    (*Queue) = (CQ*)malloc( sizeof( CQ ) );
    
    (*Queue)->CQNodes = (CQNode*)malloc( sizeof( CQNode ) * ( cap + 1 ) );
    (*Queue)->Capacity = cap;
    (*Queue)->Front = 0;
    (*Queue)->Rear = 0;
}

void CQEnqueue( CQ* Queue, ElementType data )
{
    int pos = Queue->Rear;
    if ( Queue->Rear == Queue->Capacity )
        Queue->Rear = 0;
    else
        Queue->Rear++;

    Queue->CQNodes[pos].Data = data;
}
ElementType CQDequeue( CQ* Queue )
{
    int pos = Queue->Front;
    if ( Queue->Front == Queue->Capacity )
        Queue->Front = 0;
    else
        Queue->Front++;

    return Queue->CQNodes[pos].Data;
}

void DestroyCQ( CQ* Queue )
{
    free( Queue->CQNodes );
    free( Queue );
}

큐의 크기는 CQ->Front와 CQ->Rear를 가지고 쉽게 알아낼 수 있다.

링크드 리스트 기반 큐(링크드 큐)

링크드 리스트가 배열에 비해 우리에게 익숙하지 않아서 그렇지, 생각해보면 링크드 리스트가 큐를 구현하기에 더 편하다는 것을 알 수 있다. 배열 기반의 큐는 스택과 다르게 요소를 빼낼 때마다 전단의 인덱스가 바뀌어야 해서 구조가 복잡했다. 링크드 리스트는 전단 노드와의 연결을 끊기만 하면 된다.

게다가 스택에서도 살펴본 것처럼, 용량을 미리 정할 필요가 없는 자료구조라서 순환 큐보다 유연하다.

물론, 성능은 순환 큐가 더 좋다. 링크드 큐Linked Queue는 노드 생성 및 삭제 시에 malloc과 free 함수를 호출해야 하기 때문이다.

따라서, 언제나 그렇듯, 모든 면에서 최상인 자료구조를 찾아 헤메는 것보다 적절한 때에 적절한 자료구조를 사용하고자 하는 태도가 중요하다.

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

typedef struct _LQNode
{
    char* Data;
    struct _LQNode* Next;
} LQNode;

typedef struct _LQ
{
    LQNode* Front;
    LQNode* Rear;
    int Cnt;
} LQ;

void CreateLQ( LQ** Queue )
{
    (*Queue) = ( LQ* )malloc( sizeof( LQ ) );

    (*Queue)->Front = NULL;
    (*Queue)->Rear = NULL;
    (*Queue)->Cnt = 0;
}
LQNode* CreateLQNode( char* data )
{
    LQNode* N = (LQNode*)malloc( sizeof( LQNode ) );
    
    N->Data = (char*)malloc( strlen( data ) + 1 );
    strcpy( N->Data, data );
    N->Next = NULL;

    return N;
}

void LQEnqueue( LQ* Queue, LQNode* N )
{
    if ( Queue->Front == NULL )
    {
        Queue->Front = N;
        Queue->Rear = N;
    }
    else
    {
        Queue->Rear->Next = N;
        Queue->Rear = N;
    }
    
    Queue->Cnt++;
}
LQNode* LQDequeue( LQ* Queue )
{
    LQNode* Front = Queue->Front;

    if ( Queue->Front->Next == NULL )
    {
        Queue->Front = NULL;
        Queue->Rear = NULL;
    }
    else
        Queue->Front = Queue->Front->Next;

    Queue->Cnt--;

    return Front;
}

void DestroyLQNode( LQNode* N )
{
    free( N->Data );
    free( N );
}
void DestroyLQ( LQ* Queue )
{
    while ( Queue->Front != NULL )
    {
        LQNode* Popped = LQDequeue( Queue );
        DestroyLQNode( Popped );
    }

    free( Queue );
}

참고 서적:
박상현, 2022, 한빛미디어, 『이것이 자료구조+알고리즘이다』

참고 사이트:
나무위키: 큐(자료구조)