[자로구조] 링크드 큐(Linked Queue) - 코딩밥상

링크드 리스트 기반으로 큐 구현하기

링크드 큐는 순환 큐보다 직관적으로 구현할 수 있습니다. 링크드 큐의 각 노드는 이전 노드에 대한 포인터를 이용해 연결되므로 삽입 연산을 할 떄는 삽입 하려는 노드에 후단을 연결하고, 제거 연산을 할 때는 전단 바로 다음 노드에서 전단에 대한 포인터를 거두기만 하면 됩니다.

링크드 큐와 순환 큐의 또 다른 한가지 점은 큐가 가득 찬 상태인지 확인할 필요가 없습니다. 배열 기반으로 구현한 순환큐와는 다르게 링크드 리스트 기반은 용량의 제한이 없기 때문입니다.

 

하지만 성능적으로 치면 순환 큐가 더 빠릅니다. 노드를 생성하고 삭제하기 위해 malloc()과 free()함수를 호출 할 필요가 없기 때문입니다.

따라서 필요한 큐의 크기를 미리 정할 수 있고 고성능이 요구되는 상황에서는 링크드 큐보다 순환 큐를 선택하는 것이 좋습니다.

반대로 큐의 크기가 필연적으로 변하는 경우에는 링크드 큐를 선택하면 되겠네요.

 

-노드와 링크드 큐의 구조체

typedef struct tagNode{ //노드 구조체
    char* Data;
    struct tagNode* NextNode;
} Node;

typedef struct tagCircularQueue{   //링크드 큐 구조체
    Node* Front;
    Node* Rear;
    int Count;
} LinkedQueue;

-노드의 생성과 소멸

Node* LQ_CreateNode(char* NewData){
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->Data = (char*)malloc(strlen(NewData) + 1);
    
    strcpy(NewNode->Data, NewData);
    
    NewNode->NextNode = NULL;
    
    return NewNode;
}

void LQ_DestroyNode(Node* _Node){
    free(_Node->Data);
    free(_Node);
}

-링크드 큐의 생성과 소멸

void LQ_CreateQueue(LinkedQueue** Queue){   //Heap에 링크드 큐 할당(큐 생성)
    (*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    (*Queue)->Front = NULL;
    (*Queue)->Rear = NULL;
    (*Queue)->Count = 0;
}

void LQ_DestroyQueue(LinkedQueue* Queue){ //Heap에 할당되어있던 링크드 해제(큐 소멸)
    while (!LQ_IsEmpty(Queue)) {
        Node* Popped = LQ_Dequeue(Queue);
        LQ_DestroyNode(Popped);
    }
    
    free(Queue);
}

-노드 삽입 연산(Enqueue)

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode){    //삽입 연산(Enqueue)
    if(Queue->Front == NULL){
        Queue->Front = NewNode;
        Queue->Rear = NewNode;
        Queue->Count++;
    }
    else{
        Queue->Rear->NextNode = NewNode;
        Queue->Rear = NewNode;
        Queue->Count++;
    }
}

-노드 삭제 연산(Dequeue)

Node* LQ_Dequeue(LinkedQueue* Queue){   //삭제 연산(Dequeue)
    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;
}

 

 

-큐 상태 반환(IsEmpty)

int LQ_IsEmpty(LinkedQueue* Queue){   //공백 상태 확인
    return (Queue->Front == NULL);
}