큐(Queue) - 링크드 큐

큐(Queue) - 링크드 큐

순환 큐와 링크드 큐

사실 순환 큐는 복잡한 개념을 가지고 있을 뿐더러 구현이 쉽지가 않습니다. 전단과 후단에 대한 개념은 특히 이해하기 어려울 수 있습니다.

반면 링크드 큐는 각 노드가 앞 노드에 대한 포인터를 이용하여 구성되어 있기 때문에, 삽입은 새 노드의 포인터에 후단을 연결하고 제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두어 들이는 것으로 구현할 수 있습니다.

또한, 링크드 큐는 큐가 가득 차 있는 상태인지 여부를 확인할 필요가 없습니다. 일반적으로는 용량의 한계가 없기 때문에 '가득찬다' 라는 개념이 없기 때문입니다.

하지만 순환 큐는 성능이 보다 빠르다는 장점이 있습니다. 노드를 생성하고 삭제하기 위해 malloc() 함수를 호출할 필요가 없기 때문입니다.

따라서 큐의 크기가 예측 가능하고 고성능이 필요한 버퍼와 같은 사례에는 순환 큐가 더 적절 하고, 그렇지 않을 경우 링크드 큐가 적절할 것입니다.

링크드 큐 구현하기

링크드 리스트로 큐를 표현하는 것은 순환 큐에 비해 간단합니다. 직관에 따라 설계와 구현이 가능합니다.

링크드 큐와 노드의 선언

링크드 큐의 노드는 링크드 리스트의 노드처럼 데이터 필드와 다음 노드를 가리키는 포인터로 구성됩니다.

typedef struct tagNode
{
    char* Data;
    struct tagNode* NextNode;
}    Node;

링크드 큐에서 각 노드의 데이터 필드는 문자열 char* 형입니다. 노드의 데이터 필드에 char* 가 아닌 다른 자료형을 사용하고 싶다면 그렇게 해도 좋습니다. 단, 노드를 생성하고 소멸시킬 때 데이터 필드의 메모리 관리는 자료형에 따라 적절히 대응해주어야 합니다.

typedef struct tagLinkedQueue
{
    Node*    Front;
    Node*    Rear;
    int     Count;
}    LinkedQueue;

링크드 큐의 구조체는 위와 같이 선언됩니다. 필드가 모두 세 개이며, 첫 번째는 큐의 시작(전단)을 가리키는 Front, 두 번째는 큐의 끝(후단)을 가리키는 Rear, 마지막 필드는 노드의 수를 나타내는 Count 입니다.

링크드 큐의 생성과 소멸

링크드 큐의 생성을 담당하는 함수의 이름은 LQ_CreateQueue() 이고, 소멸을 담당하는 함수의 이름은 LQ_DestroyQueue() 입니다. 링크드 큐에 관련된 함수의 이름은 모두 LQ_(Linked Queue)라는 접두사를 사용하였습니다.

먼저, LQ_CreateQueue()는 LinkedQueue 구조체를 자유 저장소에 생성하고 이 구조체의 각 필드를 초기화하는 일을 수행합니다.

void  LQ_CreateQueue( LinkedQueue** Queue )
{
    /*  큐를 자유저장소에 생성 */
    (*Queue )        = ( LinkedQueue*)malloc(sizeof( LinkedQueue ) );
    (*Queue )->Front = NULL;
    (*Queue )->Rear  = NULL;
    (*Queue )->Count = 0;
}

링크드 큐의 소멸을 담당하는 LQ_DestroyQueue() 함수는 큐 내부에 있는 모든 노드를 자유 저장소에서 제거하고 마지막에는 큐를 자유 저장소에서 제거합니다.

void LQ_DestroyQueue( LinkedQueue* Queue )
{
    while ( !LQ_IsEmpty( Queue ) )
    {
        Node* Popped = LQ_Dequeue( Queue );
        LQ_DestroyNode(Popped);    
    }

    /*  큐를 자유 저장소에서 해제 */
    free( Queue );
}

삽입(Enqueue) 연산

링크드 큐의 삽입 연산은 후단에 새로운 노드를 붙이면 됩니다. 다음 코드는 링크드 큐의 삽입 연산을 수행하는 LQ_Enqueue() 함수입니다.

void LQ_Enqueue( LinkedQueue* Queue, Node* NewNode )
{
    if ( Queue->Front == NULL ) 
    {        
        Queue->Front = NewNode;
        Queue->Rear  = NewNode;
        Queue->Count++;
    } 
    else
    {
        Queue->Rear->NextNode = NewNode;
        Queue->Rear = NewNode;
        Queue->Count++;
    }
}

제거 (Dequeue) 연산

링크드 큐의 제거 연산은 전단의 바로 다음 노드를 새로운 전단으로 만들고, 전단이었던 노드의 포인터를 호출자에게 반환하는 방식으로 구현됩니다. 다음은 제거 연산을 수행하는 LQ_Dequeue() 함수입니다.

Node* LQ_Dequeue( LinkedQueue* Queue )
{
    /*  LQ_Dequeue() 함수가 반환할 최상위 노드 */
    Node* Front = Queue->Front;

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

    Queue->Count--;

    return Front;
}

링크드 큐 예제 프로그램

링크드 큐 예제 프로그램은 LinkedQueue.h, LinkedQueue.c, Test_LinkedQueue.c 총 3개의 파일로 구성되어 있습니다.

LinkedQueue.h

#ifndef LINKED_QUEUE_H
#define LINKED_QUEUE_H

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

typedef struct tagNode
{
    char* Data;
    struct tagNode* NextNode;
} Node;

typedef struct tagLinkedQueue
{
    Node* Front;
    Node* Rear;
    int   Count;
} LinkedQueue;

void  LQ_CreateQueue( LinkedQueue** Queue );
void  LQ_DestroyQueue( LinkedQueue* Queue );

Node* LQ_CreateNode(char* Data);
void  LQ_DestroyNode(Node* _Node );

void  LQ_Enqueue( LinkedQueue* Queue, Node* NewNode );
Node* LQ_Dequeue( LinkedQueue* Queue );

int   LQ_IsEmpty( LinkedQueue* Queue );

#endif LINKED_QUEUE_H

LinkedQueue.c

#include "LinkedQueue.h"

void  LQ_CreateQueue( LinkedQueue** Queue )
{
    /*  큐를 자유저장소에 생성 */
    (*Queue )        = ( LinkedQueue*)malloc(sizeof( LinkedQueue ) );
    (*Queue )->Front = NULL;
    (*Queue )->Rear  = NULL;
    (*Queue )->Count = 0;
}

void LQ_DestroyQueue( LinkedQueue* Queue )
{
    while ( !LQ_IsEmpty( Queue ) )
    {
        Node* Popped = LQ_Dequeue( Queue );
        LQ_DestroyNode(Popped);    
    }

    /*  큐를 자유 저장소에서 해제 */
    free( Queue );
}

Node* LQ_CreateNode( char* NewData )
{
    Node* NewNode = (Node*)malloc( sizeof( Node ) );
    NewNode->Data = (char*)malloc( strlen( NewData) + 1);

    strcpy(NewNode->Data, NewData);  /*  데이터를 저장한다. */

    NewNode->NextNode = NULL; /*  다음 노드에 대한 포인터는 NULL로 초기화 한다. */

    return NewNode;/*  노드의 주소를 반환한다. */
}

void  LQ_DestroyNode(Node* _Node )
{
    free(_Node->Data);
    free(_Node );
}

void LQ_Enqueue( LinkedQueue* Queue, Node* NewNode )
{
    if ( Queue->Front == NULL ) 
    {        
        Queue->Front = NewNode;
        Queue->Rear  = NewNode;
        Queue->Count++;
    } 
    else
    {
        Queue->Rear->NextNode = NewNode;
        Queue->Rear = NewNode;
        Queue->Count++;
    }
}

Node* LQ_Dequeue( LinkedQueue* Queue )
{
    /*  LQ_Dequeue() 함수가 반환할 최상위 노드 */
    Node* Front = Queue->Front;

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

    Queue->Count--;

    return Front;
}

int LQ_IsEmpty( LinkedQueue* Queue )
{
    return ( Queue->Front == NULL);
}

Test_LinkedQueue.c

#include "LinkedQueue.h"

int main( void )
{
    Node* Popped;
    LinkedQueue* Queue;

    LQ_CreateQueue(&Queue );

    LQ_Enqueue( Queue, LQ_CreateNode("abc") );
    LQ_Enqueue( Queue, LQ_CreateNode("def") );
    LQ_Enqueue( Queue, LQ_CreateNode("efg") );
    LQ_Enqueue( Queue, LQ_CreateNode("hij") );

    printf("Queue Size : %d\n", Queue->Count);

    while ( LQ_IsEmpty( Queue ) == 0 )
    {
        Popped = LQ_Dequeue( Queue );

        printf( "Dequeue: %s \n", Popped->Data );

        LQ_DestroyNode( Popped );
    }

    LQ_DestroyQueue( Queue );

    return 0;
}