[자료구조] C로 Queue 만들기

Queue?

큐는 FIFO(First In First Out) 방식으로, 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료구조입니다. LIFO방식의 스택과 정확히 반대의 개념입니다.

동작 원리

큐는 내부적으로 배열이나 연결리스트를 이용해서 데이터를 저장합니다. 여기서는 연결리스트를 이용해서 구현하는 방법을 설명하겠습니다. 자세한 동작 원리는 코드와 함께 설명드리겠습니다.

구조체 선언

typedef struct node {
    // 저장할 데이터
    int data;
    // 다음 노드 주소값
    struct node *next;
} Node;

typedef struct {
    // 맨 앞 노드
    Node *front;
    // 맨 뒤 노드
    Node *rear;
    // 큐 사이즈
    int size;
} Queue;

Queue initQueue() {
    Queue queue;
    // 사이즈 0으로 초기화
    queue.size = 0;
    //큐의 맨 앞, 맨 뒤 노드 NULL로 초기화
    queue.front = queue.rear = NULL;
    return queue;
}

큐를 구성하는 구조체입니다. 큐는 내부적으로 연결리스트로 데이터를 저장하기 때문에 연결 리스트로 활용할 Node 구조체도 선언해 주었습니다. 큐는 맨 앞 노드와 맨 뒤 노드를 저장해서 추가, 삭제 할 떄 사용합니다.

데이터 enqueue

void enqueue(Queue *queue, int value) {
    // 새 노드 할당
    Node* newNode = (Node*)malloc(sizeof(Node));
    // 새 노드에 데이터 저장
    newNode->data = value;
    // 새 노드의 다음 노드는 NULL로 저장
    newNode->next = NULL;
    if (isEmpty(queue)) {
        // 큐가 비어있다면 앞, 뒤 모두 새 노드를 가르키도록 지정
        queue->front = queue->rear = newNode;
    } else {
        // 큐가 비어있지 않다면 뒤 노드를 새 노드로 지정
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    // 큐 사이즈 + 1
    queue->size++;
}

큐에서 enqueue 함수는 데이터를 새로 추가하는 함수입니다. 새 노드를 할당해서 큐의 start를 새 노드로 교채하는 방식으로 동작합니다. 동작 과정은 그림으로 표현하면 다음과 같습니다.

큐에 데이터가 있을 때

초기 상태가 위와 같을때, 숫자 4를 추가하는 상황을 예로 들겠습니다.

먼저 새 노드를 만들어 숫자 4를 넣고, 마지막 노드의 다음 노드를 새 노드로 지정합니다.

마지막으로 큐의 마지막 노드를 새 노드로 지정합니다.

큐에 데이터가 없을 때

큐에 비어있는 상황이라면 추가하는 로직이 조금 달라집니다.

큐에 아무런 데이터가 없다면 first와 rear 모두 NULL을 가르키고 있습니다.

새 데이터를 넣기 위해 새 노드를 생성하고 값을 넣어 줍니다.

큐의 첫 노드와 마지막 노드를 모두 새 노드로 지정합니다.

데이터 dequeue

int dequeue(Queue *queue) {
    // 큐에 데이터가 없다면 -1 리턴
    if (isEmpty(queue)) return -1;
    // 가장 첫 노드 가져옴
    Node* target = queue->front;
    // 큐의 가장 첫 노드 = 현재 가장 첫 노드의 다음 노드
    queue->front = target->next;
    // 값 가져옴
    int value = target->data;
    // 가장 첫 노드 삭제
    free(target);
    // 값 리턴
    return value;
}

큐에서 dequeue 함수는 데이터를 꺼내오는 함수입니다. 가장 첫 번째 노드의 값을 가져오고, 큐의 가장 첫 노드를 현재 첫 노드의 다음 노드로 지정합니다. 원래 가장 첫 번쨰에 있던 노드는 메모리에서 해제하여 삭제시키고, 값만 리턴합니다.

전체 코드

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

typedef struct node {
    int data;
    struct node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
    int size;
} Queue;

Queue initQueue() {
    Queue queue;
    queue.size = 0;
    queue.front = queue.rear = NULL;
    return queue;
}

int isEmpty(Queue *queue) {
    return queue->size == 0;
}

void enqueue(Queue *queue, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (isEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->size++;
}

int dequeue(Queue *queue) {
    if (isEmpty(queue)) return -1;
    Node* target = queue->front;
    queue->front = target->next;
    int value = target->data;
    free(target);
    return value;
}

void freeQueue(Queue *queue) {
    Node* currentNode = queue->front;
    while (currentNode != NULL) {
        Node* tmp = currentNode->next;
        free(currentNode);
        currentNode = tmp;
    }
}

void printQueue(Queue *queue) {
    Node* currentNode = queue->front;
    while (currentNode != NULL) {
        printf("%d ", currentNode->data);
        currentNode = currentNode->next;
    }
    printf("\n");
}

int main() {
    Queue queue = initQueue();

    char command[10];
    int number;

    printf("Commands: enqueue <num>, dequeue, exit\n");
    while (1) {
        printf("> ");
        scanf("%s", command);

        if (strcmp(command, "enqueue") == 0) {
            scanf("%d", &number);
            enqueue(&queue, number);
            printQueue(&queue);
        } else if (strcmp(command, "dequeue") == 0) {
            printf("%d\n", dequeue(&queue));
            printQueue(&queue);
        } else if (strcmp(command, "exit") == 0) {
            break;
        } else {
            printf("Invalid command.\n");
        }
    }

    freeQueue(&queue);

    return 0;
}