(C언어) 자료구조: 연결리스트(linked list)로 표현한 큐(queue)

C 언어로 연결 리스트(linked list)를 활용하여 큐(Queue)를 표현했습니다.

큐는 데이터를 FIFO(First-In-First-Out) 방식으로 처리하는 자료 구조로 먼저 입력된 자료가 먼저 출력되는 자료 구조입니다.

먼저, 연결 리스트의 노드를 정의합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.

// 큐 노드 구조체 정의
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 큐 구조체 정의
typedef struct Queue {
    QueueNode* front;  // 큐의 맨 앞 노드
    QueueNode* rear;   // 큐의 맨 뒤 노드
} Queue;

 

void initializeQueue(Queue* queue): 큐를 초기화하는 함수

void enqueue(Queue* queue, int data) 큐에 데이터를 삽입하는 함수

int dequeue(Queue* queue): 큐에서 데이터를 삭제하고, 삭제한 자료를 반환하는 함수

void clearQueue(Queue* queue): 큐를 비우는 함수

void printQueue(Queue* queue): 큐의 모든 데이터를 출력하는 함수

 

 

연결리스트(linked list)로 표현한 큐(queue)의 C언어 코드

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

// 큐 노드 구조체 정의
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 큐 구조체 정의
typedef struct Queue {
    QueueNode* front;  // 큐의 맨 앞 노드
    QueueNode* rear;   // 큐의 맨 뒤 노드
} Queue;

// 큐 초기화
void initializeQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 큐에 데이터 추가 (enqueue)
void enqueue(Queue* queue, int data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        printf("메모리 부족으로 큐에 데이터를 추가할 수 없습니다.\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;

    if (queue->rear == NULL) {
        // 큐가 비어있을 경우
        queue->front = newNode;
        queue->rear = newNode;
    }
    else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// 큐에서 데이터 제거 (dequeue)
int dequeue(Queue* queue) {
    if (queue->front == NULL) {
        printf("큐가 비어있습니다.\n");
        return -1; // 예외 처리: 큐가 비어있는 경우
    }

    int data = queue->front->data;
    QueueNode* temp = queue->front;

    if (queue->front == queue->rear) {
        queue->front = NULL;
        queue->rear = NULL;
    }
    else {
        queue->front = queue->front->next;
    }

    free(temp);
    return data;
}

// 큐 비우기
void clearQueue(Queue* queue) {
    while (queue->front != NULL) {
        dequeue(queue);
    }
}

// 큐 출력
void printQueue(Queue* queue) {
    QueueNode* current = queue->front;
    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Queue myQueue;
    initializeQueue(&myQueue);

    enqueue(&myQueue, 10);
    enqueue(&myQueue, 20);
    enqueue(&myQueue, 30);

    printQueue(&myQueue);

    int value = dequeue(&myQueue);     printf("Dequeued: %d\n", value);

    printQueue(&myQueue);
    clearQueue(&myQueue);

    value = dequeue(&myQueue);     printf("Dequeued: %d\n", value);

    return 0;
}

연결리스트(linked list)로 표현한 큐(queue)

(Output)

ueue: 10 20 30 Dequeued: 10 Queue: 20 30 큐가 비어있습니다. Dequeued: -1

(C언어) 자료구조: 연결리스트(linked list)로 표현한 큐(queue)

 

 

1. 배열로 표현한 큐의 장점:

• Random Access 가능: 배열로 구현된 큐는 인덱스를 통해 어떤 원소든 랜덤 엑세스(random access)가 가능합니다. 이것은 큐 내의 특정 원소를 빠르게 검색할 때 유용합니다.
• 메모리 효율성: 배열은 각 요소에 대한 추가 메타데이터(포인터)가 필요하지 않으므로 메모리 오버헤드가 적습니다.

 

2. 연결 리스트로 표현한 큐의 장점:

• 동적 크기 조절: 연결 리스트로 구현된 큐는 동적 크기 조절이 간편합니다. 큐의 크기가 변할 때마다 메모리를 동적으로 할당하거나 해제할 수 있습니다.
• 메모리 효율성(일부 상황에서): 연결 리스트의 노드는 포인터를 사용하여 연결되기 때문에, 메모리를 낭비하지 않고 필요한 크기만 할당할 수 있습니다.
• 삽입과 삭제 효율성: 연결 리스트로 구현된 큐는 큐의 앞과 뒤에서의 삽입 및 삭제가 매우 효율적입니다. 큐의 크기가 작거나 큐가 자주 변경될 때 특히 유용합니다.

연결 리스트로 큐를 구현하는 주요 장점은 동적 크기 조절과 효율적인 삽입/삭제 작업입니다. 크기가 미리 알려지지 않는 경우나 큐의 크기가 동적으로 변하는 경우 연결 리스트로 구현된 큐가 더 효율적일 수 있습니다. 그러나 배열로 구현된 큐는 랜덤 엑세스와 메모리 효율성 측면에서 장점을 가집니다. 따라서 선택은 사용 사례와 요구 사항에 따라 달라질 것입니다.