[알고리즘] 큐(Queue)

큐(Queue)

스택과 다르게 FIFO(First in First out), LILO(Last in Last out)구조를 가지고 있다. 자료ABCD를 순서대로 저장하면 나올때도 역시 ABCD가 나온다. 보통 쉽게 말하면 은행같은데서 순서대로 처리하기 위해 사람들을 줄세우는것을 생각하면 된다.

큐의 경우 크게 따지면 원형큐(순환큐), 링크드큐 두종류가 있다. 순환큐의 경우 배열로 구현하기 때문에 속도가 빠른 장점이 있지만 크기가 제한되어 있다는점. 링크드 큐와 다르게 큐 오버플로우(큐가 꽉차서 더이상 들어갈수 없는 상태)가 발생한다. 링크드큐의 경우 큐의 크기가 제한이 없지만, 속도가 느리다는 단점이 있다. 아래 소스에선 링크드 큐만을 구현할것이다. 순환큐의 경우 이론만 설명하고 넘어간다.

순환 큐

순환큐는 다음 그림을 떠올리면 된다.

front는 데이터의 시작부분을 가리키고, rear는 데이터가 새로 들어갈부분을 가리킨다. 삽입 삭제 연산을 Enqueue, Dequeue라고 한다. 삽입은 rear에서만 일어나고, 제거는 front에서만 일어나게 된다. 아래 그림을 보자.

위에는 큐가 꽉차는 두가지 경우를 보여준다. 왼쪽의 경우 후자에 비해 공간이 하나 더 있어 효율적으로 사용할수 있다고 생각하지만 왼쪽의 경우 저런식으로 구현하게 되면 큐가 꽉찬경우와 빈경우를 확인할수 없다는 단점이 있다. 설마 NULL==Rear->rear->Data 로 비교해서 비엇는지 안비엇는지 확인하겟다는 생각은 하지 말길 바란다.
반대로 후자의 경우는 front==rear이면 스택이 빈것으로 확인할수가 있다. 자세한 부분은 이 포스트에서 다루지 않을것이기 때문에 다른 좋은 블로그에서 나보다 훨씬 더 잘 설명햇으니 가서 참고하길 바란다.

링크드 큐

링크드 큐의 경우 스택을 구현할줄 알면 거저먹기나 마찬가지기 때문에 간단히 설명한다.

[알고리즘] 스택(Stack)

typedef struct tagNode{
    char Data[20];
    struct tagNode* NextNode;
}NODE;

typedef struct tagQueue{
    NODE* Front;
    NODE* Rear;
}QUEUE;

Queue자료구조의 경우 자료를 꺼낼 포인터 주소(Front)와 자료를 집어넣을주소(Rear)만 있으면 충분하다.


큐를 생성하는 함수와 큐를 구성하는 노드를 생성하는 함수다.

void CreateQueue(QUEUE** Queue)
{
    (*Queue) = (QUEUE*)malloc(sizeof(QUEUE));

    (*Queue)->Front = NULL;
    (*Queue)->Rear = NULL;
}

NODE* CreateNode(char Data[])
{
    NODE* NewNode = (NODE*)malloc(sizeof(NODE));

    strcpy(NewNode->Data, Data);
    NewNode->NextNode = NULL;

    return NewNode;
}

큐에 데이터를 삽입하는 Enqueue함수다.

void Enqueue(QUEUE* Queue, char Data[])
{
    if(Queue->Front == NULL)
    {
        Queue->Front = CreateNode(Data);
        Queue->Rear = Queue->Front;
    }
    else
    {
        Queue->Rear->NextNode = CreateNode(Data);
        Queue->Rear = Queue->Rear->NextNode;
    }
}

큐가 비엇으면 Front와 Rear가 새로 만들어진 노드를 가리키면 되고, 비어있지 않을경우엔 Rear만 +시켜주면 된다.



큐에서 데이터를 꺼내는 Dequeue연산이다. Front값만 변하는것을 볼수 있다. (NULL일때 빼고)

NODE* Dequeue(QUEUE* Queue)
{
    NODE* FrontNode = Queue->Front;

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

    return FrontNode;
}

밑은 따로 개인적으로 만든 함수다.

void PrintQueue(NODE* PrintNode)
{
    printf("Queue: %s\n", PrintNode->Data);
    free(PrintNode);
}

int IsEmpty(QUEUE* Queue)
{
    return (Queue->Front == NULL);
}

사용 예

int main()
{
    QUEUE* Queue;

    CreateQueue(&Queue);

    Enqueue(Queue, "짜장면");
    Enqueue(Queue, "짬뽕");

    PrintQueue(Dequeue(Queue));
    printf("\n");

    Enqueue(Queue, "군만두");
   
    // 전체 꺼내기
    while(0 == IsEmpty(Queue))
    {
        PrintQueue(Dequeue(Queue));
    }

    return 0;
}

결과화면