[자료구조] Queue(큐) 구현하기

Queue(큐)는 선입선출(FIFO; First In First Out)의 자료구조로 데이터들이 들어온 순서대로 처리되는 구조를 말합니다.

데이터 삽입이 들어오는 back/rear 부분과 데이터가 나가는 front 부분이 있습니다.
입력 동작은 Enqueue, 출력동작은 Dequeue라고 합니다.

스택과 마찬가지로 연결리스트만 완벽히 이해한다면 구현하기 쉽습니다 -> 연결리스트 구현하기

큐 구현

먼저 Node와 Queue를 만듭니다.
Queue에서는 데이터를 추가할 부분인 back, 데이터를 가져올 부분인 front를 갖고 있습니다.

typedef struct Node
{
    int data;
    Node *next;
}Node;
 
typedef struct Queue
{
    Node* front;
    Node* back;
    int count;
}Queue;

Queue를 초기화하는 InitQueue함수

void InitQueue(Queue **queue)
{
    (*queue) = (Queue*)malloc(sizeof(Queue));
    (*queue)->front = (*queue)->back = NULL;
    (*queue)->count = 0;
}

데이터를 추가하는 EnQueue함수,

데이터가 처음 추가되면 front와 back이 처음 추가되는 노드를 가르키고,
그다음부터 추가되는 노드는 Queue의 back이 된다. 각 노드는 다음의 노드를 가르키고 있는다.

Node* CreateNode(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}
 
void EnQueue(Queue **queue, Node *node)
{
    if ((*queue)->count == 0)
    {
        (*queue)->front = (*queue)->back = node;
    }
    else
    {
        (*queue)->back->next = node;
        (*queue)->back = node;
    }
 
    (*queue)->count++;
}

데이터를 가져오는 DeQueue함수

front의 노드를 가져오고, front는 front->next노드가 된다.

Node* DeQueue(Queue **queue)
{
    Node * n = (*queue)->front;
    (*queue)->front = n->next;
    (*queue)->count--;
    return n;
}

구현된 DeQueue를 사용하여 노드의 전체를 출력하는 PrintAllNode(), Queue를 메모리 해제하는 DestroyQueue()함수를 만든다.

int getNodeCount(Queue **queue)
{
    return (*queue)->count;
}
 
void DestroyQueue(Queue** queue)
{
    int cnt = getNodeCount(queue);
    for (int i = 0; i < cnt; i++)
    {
        Node * n = DeQueue(queue);
        free(n);
    }
    (*queue)->front = (*queue)->back = NULL;
    (*queue)->count = 0;
    free(*queue);
}
 
void PrintAllNode(Queue** queue)
{
    int cnt = getNodeCount(queue);
    for (int i = 0; i < cnt; i++)
    {
        Node * n = DeQueue(queue);
        cout << n->data << endl;
        free(n);
    }
}

그리고 다음과 같이 테스트해보면 됩니다.

int main()
{
    Queue *queue = NULL;
    InitQueue(&queue);
    EnQueue(&queue, CreateNode(1));
    EnQueue(&queue, CreateNode(2));
    EnQueue(&queue, CreateNode(3));
    EnQueue(&queue, CreateNode(4));
    EnQueue(&queue, CreateNode(5));
    EnQueue(&queue, CreateNode(101));
    EnQueue(&queue, CreateNode(102));
    EnQueue(&queue, CreateNode(103));
    EnQueue(&queue, CreateNode(104));
    EnQueue(&queue, CreateNode(105));
    PrintAllNode(&queue);
    EnQueue(&queue, CreateNode(1));
    EnQueue(&queue, CreateNode(2));
    EnQueue(&queue, CreateNode(3));
    EnQueue(&queue, CreateNode(4));
    EnQueue(&queue, CreateNode(5));
    PrintAllNode(&queue);
    return 0;
}