[c언어] 큐(Queue)

안녕하세요 업글입니다! 이번 포스팅에서는 큐에 대해서 설명해보도록 하겠습니다.

 

자료구조 중 하나인 큐(Queue)는 많은 분들이 알고계시고 프로그래밍을 막 시작하신 분들도 한번쯤은 들어봤을만한 대표적인 자료구조 중 하나라고 생각합니다.

 

큐에 대한 설명

큐는 입력된 데이터들을 순서대로 저장하고 순서대로 출력하는 자료구조입니다. 큐의 가장 큰 특징은 먼저 들어온 데이터는 먼저 나가는 것입니다. 이것을 선입선출 또는 FIFO이라고 주로 표현합니다. 쉽게 예를 들어서 맛집에서 줄서기를 생각하시면 될 것 같습니다. 먼저 온 사람이 맛집에 먼저 들어가고 나중에 온 사람이 나중에 들어가는 것과 같이 데이터가 관리되게 됩니다.

 

큐 사용 이유

큐는 bfs(breath first search)와 같은 탐색 알고리즘 등에서 사용되기도 하지만 즉시 처리하지 못하는 상황에 주로 사용됩니다. 비동기 시스템에서 주로 사용된다고 생각하시면 될 것 같습니다.

 

비동기 통신을 예시로 설명하겠습니다.

A쓰레드에서는 데이터를 송신하고 B쓰레드에서는 데이터를 수신하여 쓰레드 간 통신하는 경우로 가정하겠습니다. 이 때 데이터를 송신하는 시점과 수신하는 시점이 달라서 비동기인 상황에서는 데이터를 송신했을 때 수신하는 쓰레드에서 수신 데이터를 즉시 처리할 수 없습니다. 이러한 상황에서 A쓰레드에서 데이터들을 큐에 입력하고 B쓰레드에서는 처리 가능한 시간에 큐에서 데이터를 출력하여 처리함으로써 비동기 상황에서 데이터를 문제없이 수신하여 처리할 수 있습니다.

 

이러한 경우 뿐만 아니라 데이터가 수신될 때 수신된 데이터 파싱과 같은 작업을 즉시 처리할 수 있는 시간이 부족한 경우 큐에 데이터만 입력하고 데이터가 수신되지 않거나 여유있는 시간에 큐에서 데이터를 출력하여 문제없이 처리 할 수 있습니다.

 

큐 구현 방법

큐는 배열과 링크드리스트를 사용하여 구현할 수 있습니다. 배열의 경우 선형큐와 원형큐로 구분할 수 있지만 선형큐의 경우 사용하기에 적절하지 않기 때문에 원형큐를 사용하게 됩니다. c++의 경우 STL을 사용하여 쉽게 검증된 큐를 사용하실 수 있습니다.

 

1. 배열을 통해 원형큐를 구현하는 경우

back값은 데이터가 입력 되어야 할 인덱스 위치, front값은 데이터가 출력 되어야 할 인덱스 위치입니다. 마지막 인덱스까지 데이터를 입력하거나 출력했을 때(back값 또는 front값이 마지막 인덱스 값일 때)는 다시 첫번째 인덱스(back값 또는 front값이 0)에 데이터를 입력하거나 출력하도록 구현합니다. 최대로 입력될 수 있는 크기를 고려하여 배열을 크기를 선정하는 것이 중요합니다.

 

아래의 그림은 큐 크기가 4인 큐에 데이터를 1 ~ 5까지 push하고 pop을 한번하는 과정입니다.

2. 링크드리스트를 통해 큐를 구현하는 경우

front가 가르키는 노드를 출력하고 back의 다음 노드에 입력된 노드를 연결하여 구현하도록 합니다. front는 가장 앞의 노드를 가르키게 되며 back은 가장 마지막의 노드를 가르키게 됩니다. 데이터를 입력할 때는 마지막 노드의 뒤에 추가된 데이터 노드를 이어서 입력하게 되고, 데이터를 출력할 때는 첫번째 노드의 데이터를 출력하고 다음 노드를 첫번째 노드로 가르키도록 합니다. 링크드리스트를 통해서 큐를 구현하면 큐의 최대 크기를 고려하지 않고 구현할 수 있는 장점이 있습니다.

 

아래의 그림은 큐에 1 ~ 3까지 push하고 1번 pop을 한번하는 과정입니다.

배열을 이용한 큐 코드

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

#define NO (0)
#define YES (!NO)

typedef struct {
    int32_t front;
    int32_t back;
    int32_t size;
    int32_t bufSize;
    int32_t* buf;
}ST_Queue;

int32_t IsQueueEmpty(ST_Queue * queue)
{
    int32_t result;

    if (queue->size == 0) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

int32_t IsQueueFull(ST_Queue* queue)
{
    int32_t result;

    if (queue->size == queue->bufSize) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

int32_t QueueSize(ST_Queue* queue)
{
    int32_t result;

    result = queue->size;

    return result;
}

int32_t QueueInit(ST_Queue* queue, int32_t queueLength)
{
    int32_t result;

    queue->buf = (int32_t*)malloc(sizeof(int32_t) * queueLength);

    if (queue->buf != NULL) {
        queue->front = 0;
        queue->back = 0;
        queue->size = 0;
        queue->bufSize = queueLength;
        memset(queue->buf, 0, (sizeof(int32_t) * queueLength));
        result = YES;
    }
    else {
        result = NO;
    }
    
    return result;
}

void QueueDelete(ST_Queue* queue)
{
    free(queue->buf);
}

void QueuePush(ST_Queue* queue, int32_t data)
{
    if (IsQueueFull(queue) == YES) {
        printf("queue is full\n");
    }
    else {
        queue->buf[queue->back] = data;
        queue->back++;
        queue->size++;

        if (queue->back == queue->bufSize) {
            queue->back = 0;
        }
    }
}

int32_t QueuePop(ST_Queue* queue)
{
    int32_t result = 0;

    if (IsQueueEmpty(queue) == YES) {
        printf("queue is emtpy\n");
    }
    else {
        result = queue->buf[queue->front];
        queue->front++;
        queue->size--;

        if (queue->front == queue->bufSize) {
            queue->front = 0;
        }
    }

    return result;
}

int main()
{
    #define QUEUE_LENGTH (4)

    ST_Queue queue;
    int32_t i, data, loop;

    if (QueueInit(&queue, QUEUE_LENGTH) == NO) {
        printf("queue init fail\n");
    }

    /* push test */
    for (i = 0; i < QUEUE_LENGTH; i++) {
        QueuePush(&queue, i);
        printf("pushData = %d, queueSize = %d\n", i, QueueSize(&queue));
    }

    data = QUEUE_LENGTH;
    QueuePush(&queue, data);
    printf("pushData = %d, queueSize = %d\n", data, QueueSize(&queue));

    /* pop test */
    loop = QueueSize(&queue);
    for (i = 0; i < loop; i++) {
        data = QueuePop(&queue);
        printf("popData = %d, queueSize = %d\n", data, QueueSize(&queue));
    }
    
    data = QueuePop(&queue);
    printf("popData = %d, queueSize = %d\n", data, QueueSize(&queue));

    return 0;
}

 

링크드리스트를 이용한 큐 코드

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

#define NO (0)
#define YES (!NO)

typedef struct ST_Node{
    int32_t data;
    ST_Node* next;
}ST_Node;

typedef struct {
    ST_Node* front;
    ST_Node* back;
    int32_t size;
}ST_Queue;

int32_t IsQueueEmpty(ST_Queue* queue)
{
    int32_t result;

    if (queue->size == 0) {
        result = YES;
    }
    else {
        result = NO;
    }

    return result;
}

int32_t QueueSize(ST_Queue* queue)
{
    int32_t result;

    result = queue->size;

    return result;
}

int32_t QueueInit(ST_Queue* queue)
{
    int32_t result = YES;

    queue->front = NULL;
    queue->back = NULL;
    queue->size = 0;    

    return result;
}

void QueueDelete(ST_Queue* queue)
{
    int32_t i;
    ST_Node* temp;

    for (i = 0; i < queue->size; i++) {
        temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
    }

    queue->front = NULL;
    queue->back = NULL;
    queue->size = 0;
}

void QueuePush(ST_Queue* queue, int32_t data)
{
    ST_Node* addNode;

    addNode = (ST_Node*)malloc(sizeof(ST_Node));

    if (addNode == NULL) {
        printf("heap is full\n");
    }
    else {
        addNode->data = data;
        addNode->next = NULL;

        if (IsQueueEmpty(queue) == YES) {
            queue->front = addNode;
            queue->back = addNode;
        }
        else {
            queue->back->next = addNode;
            queue->back = addNode;
        }
        queue->size++;
    }
}

int32_t QueuePop(ST_Queue* queue)
{
    int32_t result = 0;
    ST_Node* del;

    if (IsQueueEmpty(queue) == YES) {
        printf("queue is emtpy\n");
    }
    else {
        result = queue->front->data;
        del = queue->front;
        queue->front = queue->front->next;
        queue->size--;

        free(del);
    }

    return result;
}

int main()
{
#define QUEUE_LENGTH (4)

    ST_Queue queue;
    int32_t i, data, loop;

    if (QueueInit(&queue) == NO) {
        printf("queue init fail\n");
    }

    /* push test */
    for (i = 0; i < QUEUE_LENGTH; i++) {
        QueuePush(&queue, i);
        printf("pushData = %d, queueSize = %d\n", i, QueueSize(&queue));
    }

    /* pop test */
    loop = QueueSize(&queue);
    for (i = 0; i < loop; i++) {
        data = QueuePop(&queue);
        printf("popData = %d, queueSize = %d\n", data, QueueSize(&queue));
    }
    
    data = QueuePop(&queue);

    QueueDelete(&queue);

    return 0;
}

이상 큐에 대한 설명을 마치겠습니다.