라이크위키

큐 (Queue) - 큐의 주요 기능, 순환 큐

IT/알고리즘
반응형

큐 (Queue) - 큐의 주요 기능, 순환 큐

큐 (Queue) - 큐의 주요 기능, 순환 큐

은행에서 먼저 온 순서대로 대기하는 줄을 만들어서 먼저 온 사람이 먼저 일을 보고 갈 수 있게 하듯이, 먼저 들어가고 먼저 나오는(FIFO(First In First Out), 또는 선입선출(先入先出)) 자료구조를 큐(Queue)라고 합니다.

큐는 작업을 처리하는 요소에 부하를 주지 않으면서도 처리 능력을 넘어서는 작업들도 놓치지 않고 수용할 수 있도록 돕는 역할을 합니다. 큐가 이처럼 '완충장치' 역할을 하는 사례는 아주 많습니다. 놀이공원의 롤러코스터에서 30인승 롤러코스터에 200명의 손님이 몰린다면, 롤러코스터는 자신의 능력 한계치인 30명을 태워서 레일로 나가고 나머지 170명은 큐에서 기다립니다. 손님이 몰린다고 하여 30명이 정원인 롤러코스터에 50명을 태우지는 않습니다.

큐의 주요 기능: 삽입과 제거

큐의 형태
큐의 형태

큐는 위와 같이 생겼습니다. 큐의 가장 앞 요소를 가리켜 전단(前段, Front), 그리고 가장 마지막 요소를 가리켜 후단(後段, Rear)이라고 합니다.

스택은 삽입과 제거가 모두 최상위 노드(Top) 한쪽에서만 이루어졌습니다. 하지만 큐는 삽입(Enqueue)은 후단, 제거(Dequeue)는 전단에서 각각 수행됩니다.

다시말해, 삽입은 후단에 노드를 덧붙여서 새로운 후단을 만드는 연산이고, 제거는 전단의 노드를 없애서 전단 뒤에 있는 노드를 새로운 전단으로 만드는 연산입니다.

순환큐

큐를 배열로 구현해야 한다면 어떨까요? 먼저 제거 연산을 떠올려보면 다음과 같을 수 있습니다.

배열로 구현한 큐의 삭제

위 그림에 있는 큐 배열의 크기는 5이며 그 안에는 1, 2, 3, 4, 5 의 값을 가진 요소가 있습니다. 전단인 1을 제거하면 배열 내에 첫 번째 인덱스의 요소는 비게 되고 빈 자리를 채우기 위해 뒤에 있던 2, 3, 4, 5 요소가 앞으로 한 칸씩 옮겨옵니다.

이 방식의 문제점이 무엇일까요? 바로 전단을 제거한 후 나머지 요소들을 한 칸씩 앞으로 옮기는 데에 드는 비용입니다. 큐의 용량이 100개라면 한 번의 제거 연산에 99번의 이동이 필요하게 됩니다. 이 정도 성능이라면 구현이 아무리 간단하더라도 사용되기 어려운 수준일 것입니다.

큐 배열 요소의 부하 문제 해결법

이 문제를 해결할 수 있는 방법은 전단을 가리키는 변수를 도입하여 배열 내의 요소를 옮기는 대신 변경된 전단의 위치만 관리하는 것입니다. 이와 함께 후단을 가리키는 변수도 도입하여 삽입이 일어날 때마다 변경되는 후단의 위치를 관리합니다. 후단을 가리키는 변수에는 실제 후단의 위치보다 1을 더한 값을 가집니다.

이렇게 하면 배열 요소들의 이동으로 인한 부하 문제는 해결할 수 있습니다. 그런데 새로운 문제가 또 발생합니다. 제거 연산을 수행할 수록 가용 용량도 줄어들기 때문입니다.

순환 큐

그렇기 때문에 등장한 것이 순환 큐 입니다. 시작과 끝을 연결해서 순환하도록 고안된 큐를 '순환 큐(Circular Queue)'라고 합니다. 실제 배열의 시작과 끝을 연결하는 것이 아닌 논리적인 개념으로, 이러한 개념을 코드로 구현해야 합니다.

비어 있거나 가득 차 있거나

순환 큐 비어있거나 가득 차 있거나

하지만 순환 큐의 문제는 아직 존재합니다. 순환 큐는 비어 있는 상태와 가득 차 있는 상태를 구분할 수가 없기 때문입니다. 순환 큐의 구현에서 후단을 실제의 후단에 1을 더한 값을 가진다는 것을 기억해야 합니다.

순환 큐 문제 해결책

이 문제를 어떻게 해결하면 좋을까요? 일반적인 해결책은 큐 배열을 생성할 때에 실제의 용량보다 1만큼 더 크게 만들어서 전단과 후단(실제의 후단)사이를 비우는 것입니다. 이렇게 하면 큐가 비어있을 때 전단과 후단은 같은 곳을 가리키게 되고 큐가 가득 차 있을 때에는 후단이 전단보다 1 작은 값을 가지게 됩니다.

순환 큐 구현하기

모든 문제가 해결되었으니 이론을 바탕으로 어떻게 구현할 것인지에 대한 이야기를 해보도록 하겠습니다.

순환 큐의 선언

순환 큐의 노드는 다음과 같은 구조체로 표현됩니다. 링크드 리스트나 스택에서 사용해왔던 노드 구조체와 같은 모습을 하고 있습니다.

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
}    Node;

순환 큐를 나타내는 CircularQueue 구조체는 Queue의 용량(Capacity), 전단의 위치(Front), 후단의 위치(Rear), 그리고 순환 큐 요소의 배열에 대한 포인터를 가지고 있습니다.

typedef struct tagCircularQueue
{
    int        Capacity;    /* 용량 */
    int        Front;        /* 전단의 인덱스 */
    int        Rear;        /* 후단의 인덱서 */
    Node*    Nodes;        /* 노드 배열 */
}    CircularQueue;

CircularQueue 구조체의 Nodes 포인터가 가리키는 배열은 자유 저장소에 생성됩니다. Capacity에는 배열의 크기, 즉 큐의 용량이 저장되는데 Capacity가 가지는 값은 실제의 용량보다 하나 작습니다. 순환 큐에는 공백/포화 상태 구분을 위한 더미 노드(Dummy Node)를 위해 한 개의 공간을 더 가지고 있기 때문입니다.

그리고 Front는 전단의 위치를, Rear는 후단의 위치를 가리킵니다. 이들이 가지는 값은 실제의 메모리 주소는 아니고 배열 내의 인덱스입니다. Rear는 실제의 후단보다 1 더 큰 값을 갖는다는 것을 기억하시기 바랍니다.

순환 큐의 생성과 소멸

다음은 순환 큐 구조체를 자유 저장소에 생성하는 CQ_CreateQueue() 함수입니다. CQ는 CircularQueue를 줄인 것입니다. CQ_CreateQueue()는 순환 큐에 대한 포인터의 포인터인 Queue와 용량을 결정하는 Capaciry를 매개 변수로 받습니다.

매개 변수를 받아들인 CQ_CreateQueue() 함수는 가장 먼저 순환 큐를 자유 저장소에 생성하고 Node의 크기 x (Capacity + 1)의 크기로 배열을 자유 저장소에 할당합니다. 앞서 말했듯 배열이 실제 데이터가 담길 공간보다 1만큼 더 큰 이유는 순환 큐가 공백 상태인지 포화 상태인지 여부를 구분하는 더미노드가 필요하기 때문입니다.

void  CQ_CreateQueue( CircularQueue** Queue, int Capacity)
{
    /*  큐를 자유저장소에 생성 */
    (*Queue )           = ( CircularQueue*)malloc(sizeof( CircularQueue ));

    /*  입력된 Capacity+1 만큼의 노드를 자유저장소에 생성 */
    (*Queue )->Nodes    = (Node*)malloc(sizeof(Node )* ( Capacity+1) );

    (*Queue )->Capacity = Capacity;
    (*Queue )->Front = 0;
    (*Queue )->Rear  = 0;
}

순환 큐를 자유 저장소에서 제거하는 CQ_DestroyQueue() 함수에서는 배열을 먼저 자유 저장소에서 제거한 후, 순환 큐 구조체를 제거하는 내용을 가집니다.

void CQ_DestroyQueue( CircularQueue* Queue )
{
    free(Queue->Nodes);
    free(Queue );
}

삽입(Enqueue) 연산

삽입 연산은 후단의 위치를 가리키는 Rear를 살피고 잘 다루는 것이 포인트입니다.

아래의 CQ_Enqueue() 함수에 if/else 블록의 if 블록에서 Rear의 값이 *Queue -> Capacity + 1과 같은 값을 가지고 있다면 후단이 배열의 끝에 도달했다는 것을 의미하므로 Rear와 Position을 0으로 지정합니다. 그렇지 않은 경우에는 else 블록으로 넘어가서 현재 Rear의 위치를 Position에 저장하고 Rear를 1 증가시킵니다.

그리고 if/else 블록이 끝난 이후에 Nodes 배열에서 Position이 가리키는 곳에 데이터를 저장합니다.

void CQ_Enqueue( CircularQueue* Queue, ElementType Data)
{
    int Position=0;

    if(Queue->Rear==Queue->Capacity)
    {
        Position=Queue->Rear;
        Queue->Rear=0;
    }
    else
        Position=Queue->Rear++;

    Queue->Nodes[Position].Data=Data;
}

제거(Dequeue) 연산

순환 큐의 제거 연산에서는 전단을 잘 다루는 것이 중요합니다.

다음 CQ_Dequeue() 합수를 보면 가장 먼저 전단의 위치(Front)를 Position에 저장합니다. 이 값은 마지막에 함수를 종료하면서 전단의 데이터를 반환할 때에 배열의 인덱스로 사용됩니다.

ElementType CQ_Dequeue( CircularQueue* Queue )
{
    int Position = Queue->Front;

    if ( Queue->Front == Queue->Capacity )
        Queue->Front = 0;
    else
        Queue->Front++;

    return Queue->Nodes[Position].Data;
}

그리고 가운데의 if/else 블록에서는 Front의 값이 Capacity와 같을 때 Front를 0으로 초기화하고, 그렇지 않으면 Front의 값을 1만큼 증가시킵니다. Front의 값이 Capacity와 같다는 것은 전단이 곧 배열의 끝에 도달해 있는 것이라는 사실을 의미합니다.

공백 상태 확인

순환 큐의 공백 상태를 확인하는 CQ_IsEmpty() 함수입니다. 전단과 후단읙 밧이 같으면 공백이라고 판정합니다.

int CQ_IsEmpty( CircularQueue* Queue )
{
    return (Queue->Front == Queue->Rear);
}

포화 상태 확인

순환 큐의 포화 상태를 확인하는 CQ_IsFull() 함수입니다.

이는 두 가지 경우의 수를 고려해야 합니다. 순환 큐 배열 내에서 전단이 후단 앞에 위치하는 경우 후단과 전단의 차가 큐의 용량과 동일한 지 여부를 확인해야 하고, 전단이 후단 뒤에 위치하는 경우 Rear에 1을 더한 값이 Front와 같은지 여부를 확인해야 합니다.

int CQ_IsFull( CircularQueue* Queue )
{
    if ( Queue->Front < Queue->Rear )
        return ( Queue->Rear - Queue->Front) == Queue->Capacity;
    else
        return ( Queue->Rear + 1 ) == Queue->Front;
}

순환 큐 예제 프로그램

프로그램은 세 개의 소스 코드 파일로 구성됩니다. CircularQueue.h와 CircularQueue.c는 순환 큐의 연산을 함수로 구현하고 있고, Test_CircularQueue.c는 이 함수들을 테스트합니다.

CircularQueue.h

#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

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

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
} Node;

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

    Node* Nodes;
} CircularQueue;

void        CQ_CreateQueue( CircularQueue** Queue, int Capacity);
void        CQ_DestroyQueue( CircularQueue* Queue );
void        CQ_Enqueue( CircularQueue* Queue, ElementType Data);
ElementType CQ_Dequeue( CircularQueue* Queue );
int         CQ_GetSize( CircularQueue* Queue );
int         CQ_IsEmpty( CircularQueue* Queue );
int         CQ_IsFull( CircularQueue* Queue );

#endif

CircularQueue.c

#include "CircularQueue.h"

void  CQ_CreateQueue( CircularQueue** Queue, int Capacity)
{
    /*  큐를 자유저장소에 생성 */
    (*Queue )           = ( CircularQueue*)malloc(sizeof( CircularQueue ));

    /*  입력된 Capacity+1 만큼의 노드를 자유저장소에 생성 */
    (*Queue )->Nodes    = (Node*)malloc(sizeof(Node )* ( Capacity+1) );

    (*Queue )->Capacity = Capacity;
    (*Queue )->Front = 0;
    (*Queue )->Rear  = 0;
}

void CQ_DestroyQueue( CircularQueue* Queue )
{
    free(Queue->Nodes);
    free(Queue );
}

void CQ_Enqueue( CircularQueue* Queue, ElementType Data)
{
    int Position=0;

    if(Queue->Rear==Queue->Capacity)
    {
        Position=Queue->Rear;
        Queue->Rear=0;
    }
    else
        Position=Queue->Rear++;

    Queue->Nodes[Position].Data=Data;
}

ElementType CQ_Dequeue( CircularQueue* Queue )
{
    int Position = Queue->Front;

    if ( Queue->Front == Queue->Capacity )
        Queue->Front = 0;
    else
        Queue->Front++;

    return Queue->Nodes[Position].Data;
}

int CQ_GetSize( CircularQueue* Queue )
{
    if ( Queue->Front <= Queue->Rear )
        return Queue->Rear - Queue->Front;
    else
        return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;
}

int CQ_IsEmpty( CircularQueue* Queue )
{
    return (Queue->Front == Queue->Rear);
}

int CQ_IsFull( CircularQueue* Queue )
{
    if ( Queue->Front < Queue->Rear )
        return ( Queue->Rear - Queue->Front) == Queue->Capacity;
    else
        return ( Queue->Rear + 1 ) == Queue->Front;
}

Test_CircularQueue.c

#include "CircularQueue.h"

int main( void )
{
    int i;
    CircularQueue* Queue;

    CQ_CreateQueue(&Queue, 10);

    CQ_Enqueue( Queue, 1 );
    CQ_Enqueue( Queue, 2 );
    CQ_Enqueue( Queue, 3 );
    CQ_Enqueue( Queue, 4 );

    for ( i=0; i<3; i++)
    {
        printf( "Dequeue: %d, ",       CQ_Dequeue( Queue ) );
        printf( "Front:%d, Rear:%d\n", Queue->Front, Queue->Rear );
    }

    i = 100;
    while ( CQ_IsFull( Queue ) == 0 )
    {
        CQ_Enqueue( Queue, i++ );
    }

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

    while ( CQ_IsEmpty( Queue ) == 0)
    {        
        printf( "Dequeue: %d, ",       CQ_Dequeue( Queue ) );
        printf( "Front:%d, Rear:%d\n", Queue->Front, Queue->Rear );
    }

    CQ_DestroyQueue( Queue );

    return 0;
}
반응형

'IT > 알고리즘' 카테고리의 다른 글

스택 응용하기 - 사칙연산 계산기 만들기  (0) 2020.07.15
링크드 리스트로 구현하는 스택  (0) 2020.07.01
스택(Stack)의 개념 및 배열로 구현하는 스택  (0) 2020.06.26
환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List)  (0) 2020.06.25
더블 링크드 리스트(Doubly Linked List)  (0) 2020.06.23

공유하기

facebook twitter kakaoTalk kakaostory naver band

'IT/알고리즘' 의 관련글

loading

티스토리툴바