[자료구조] 링크드 큐(Linked Queue)

링크드 큐(Linked Queue)

---

• 링크드 리스트를 이용하여 큐를 구현

• 노드 멤버의 포인터를 이용하여 삽입 / 제거 연산이 이루어짐

  • 삽입을 할 때는 삽입하려는 노드에 후단을 연결

    • 제거를 할 때는 전단 바로 다음 노드에 전단에 대한 포인터를 거두기만 하면 됨

• 원형 큐(순환 큐)와 다른 점은 용량 제한이 없다는 것이다.(가득 찼는지 확인할 필요 X)

링크드 큐의 기본 연산

• 보다 직관적으로 설계 및 구현이 가능함

링크드 큐와 노드의 선언

• 노드의 경우 데이터 필드와 다음 노드에 대한 포인터를 담는다

• 링크드 큐 구조체의 경우 전단, 후단, 노드 개수를 담는다

// 노드 구조체
typedef struct _Node
{
    char* data;             // 노드에 담을 데이터
    struct _Node* nextNode;     // 다음 노드에 대한 포인터
} Node;

// 링크드 큐 구조체
typedef struct _LinkedQueue
{
    Node* front;     // 전단을 가리킴
    Node* rear;      // 후단을 가리킴
    int count;       // 노드 개수
} LinkedQueue;

링크드 큐 생성

• 구조체 생성 및 각 필드 초기화

void CreateQueue(LinkedQueue** queue)
{
    // 큐 생성
    (*queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));

    // 필드 초기화
    (*queue)->front = NULL;
    (*queue)->rear = NULL;
    (*queue)->count = 0;
}

링크드 큐 소멸

• 큐 내부에 있는 모든 노드를 메모리에서 제거하고 마지막에는 큐도 제거

void DestroyQueue(LinkedQueue* queue)
{
    // 큐가 공백상태가 될 때 까지 제거
    while(!IsEmpty(queue)) {
        Node* temp = Dequeue(queue);
        DestroyNode(temp);
    }

    // 큐 삭제
    free(queue);
}

노드 삽입 연산

• 후단에 새로운 노드를 붙여주기만 하면 됨

void Enqueue(LinkedQueue* queue, Node* newNode)
{
    // 전단이 없는 경우 처음 노드 생성임
    if(queue->front == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
        queue->count++;
    }
    // 다음 노드에 삽입할 노드 할당
    else {
        queue->rear->nextNode = newNode;
        queue->rear = newNode;
        queue->count++;
    }
}

노드 제거 연산

• 전단 뒤에 있는 노드를 새로운 전단으로 만들고, 전단이었던 노드 포인터를 호출자에게 반환

Node* Dequeue(LinkedQueue* queue)
{
    // 반환할 최상위 노드
    Node* front = queue->front;

    if(queue->front->nextNode == NULL) {
        queue->front = NULL;
        queue->rear = NULL;
    }
    // 전단 뒤에 있는 노드를 새로운 노드로 만듦
    else {
        queue->front = queue->front->nextNode;
    }

    queue->count--;

    return front;
}

노드 공백 상태 확인

• front의 여부만 확인

int IsEmpty(LinkedQueue* queue)
{
    return queue->front == NULL;
}

예제 프로그램

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

typedef struct _Node
{
    char* data;             // 노드에 담을 데이터
    struct _Node* nextNode;     // 다음 노드에 대한 포인터
} Node;

typedef struct _LinkedQueue
{
    Node* front;     // 전단을 가리킴
    Node* rear;      // 후단을 가리킴
    int count;       // 노드 개수
} LinkedQueue;

void CreateQueue(LinkedQueue** queue);
void DestroyQueue(LinkedQueue* queue);

Node* CreateNode(char* newData);
void DestroyNode(Node* node);

void Enqueue(LinkedQueue* queue, Node* newNode);
Node* Dequeue(LinkedQueue* queue);

int IsEmpty(LinkedQueue* queue);

int main() 
{
    Node* temp;
    LinkedQueue* queue;

    CreateQueue(&queue);

    Enqueue(queue, CreateNode("abc"));
    Enqueue(queue, CreateNode("def"));
    Enqueue(queue, CreateNode("ghi"));
    Enqueue(queue, CreateNode("jkl"));

    printf("Queue Size : %d\n", queue->count);

    while(IsEmpty(queue) == 0) {
        temp = Dequeue(queue);

        printf("Deque : %s\n", temp->data);

        DestroyNode(temp);
    }

    DestroyQueue(queue);

    return 0;
}

void CreateQueue(LinkedQueue** queue)
{
    // 큐 생성
    (*queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));

    // 필드 초기화
    (*queue)->front = NULL;
    (*queue)->rear = NULL;
    (*queue)->count = 0;
}

void DestroyQueue(LinkedQueue* queue)
{
    // 노드가 있을 경우 삭제
    while(!IsEmpty(queue)) {
        Node* temp = Dequeue(queue);
        DestroyNode(temp);
    }

    // 큐 삭제
    free(queue);
}

Node* CreateNode(char* newData)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = (char*)malloc(strlen(newData) + 1);

    // 데이터 저장
    strcpy(newNode->data, newData);

    // 다음 노드에 대한 포인터는 NULL로 초기화
    newNode->nextNode = NULL;

    // 노드 주소 반환
    return newNode;
}

void DestroyNode(Node* node)
{
    free(node->data);
    free(node);
}

void Enqueue(LinkedQueue* queue, Node* newNode)
{
    // 전단이 없는 경우 처음 노드 생성임
    if(queue->front == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
        queue->count++;
    }
    // 다음 노드에 삽입할 노드 할당
    else {
        queue->rear->nextNode = newNode;
        queue->rear = newNode;
        queue->count++;
    }
}

Node* Dequeue(LinkedQueue* queue)
{
    // 반환할 최상위 노드
    Node* front = queue->front;

    if(queue->front->nextNode == NULL) {
        queue->front = NULL;
        queue->rear = NULL;
    }
    // 전단 뒤에 있는 노드를 새로운 노드로 만듦
    else {
        queue->front = queue->front->nextNode;
    }

    queue->count--;

    return front;
}

int IsEmpty(LinkedQueue* queue)
{
    return queue->front == NULL;
}

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)