(C) 자료구조 - 연결 자료구조를 이용한 큐의 구현 (연결 큐)

- 순차 자료구조를 이용한 큐의 단점

1. 사용 크기가 배열 크기로 제한되므로 큐의 길이를 마음대로 사용할 수 없다.

2. 원소가 없어도 항상 고정된 크기를 유지해야 하므로 메모리가 낭비된다.

--> 연결 자료구조를 이용해 크기 제한이 없는 연결 큐를 통해 한계점 보완.

 

- 연결 큐

연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째 노드를 가리키는 front 포인터와 마지막 노드를 가리키는 rear 포인터를 사용한다.

 

연결 큐의 초기 상태(공백 큐)는 front와 rear를 NULL 포인터로 설정하여 표현한다.

 

                                                                                <연결 큐의 구조>

 

 

- 연결 큐의 대한 연산 알고리즘

- 연결 큐의 노드 구조체

#pragma once
typedef char element;            // 연결 큐 원소(element)의 자료형을 char로 정의
 
typedef struct QNode {            // 연결 큐의 노드를 구조체로 정의
    element data;
    struct QNode* link;
} QNode;
 
typedef struct {                    // 연결 큐에서 사용하는 포인터 front와 rear를 구조체로 정의
    QNode* front, * rear;
} LQueueType;
 

 

1. 공백 연결 큐 생성

초기에 생성한 연결 큐는 저장된 노드가 없는 공백 연결 큐이므로 front와 rear를 NULL로 초기화한다.

// 공백 연결 큐를 생성하는 연산
LQueueType* createLinkedQueue(void) {
    LQueueType* LQ;
    LQ = (LQueueType*)malloc(sizeof(LQueueType));
    LQ->front = NULL;
    LQ->rear = NULL;
    return LQ;
}

 

2. 연결 큐의 공백 상태 검사

연결 큐가 공백 상태이면 연결된 노드가 하나도 없어서 front가 NULL이므로 다음과 같이 검사한다.

// 연결 큐가 공백 상태인지 검사하는 연산
int isLQEmpty(LQueueType* LQ) {
    if (LQ->front == NULL) {
        printf(" Lineked Queue is empty! ");
        return 1;
    }
    else return 0;
}

 

3. 연결 큐의 원소 삽입

연결 자료구조를 이용하여 구현하는 연결 큐는 크기를 정해 놓지 않고 필요할 때마다 노드를 하나씩 생성하여 연결하는 방식이기 때문에 순차 큐나 원형 큐에서와 같은 포화 상태가 존재하지 않는다.

 

1) 원소를 삽입할 새 노드에  메모리를 할당받고 데이터 필드에 삽일할 데이터 item을 저장한다. 삽입하는 새 노드는 연결 큐의 마지막 노드가 되어야하므로 링크 필드에 NULL을 저장한다.

2) 새 노드를 삽입하기 전에 연결 큐가 공백 상태인지 검사한다. 연결 큐가 공백 상태이면 삽일할 새 노드가 큐의 첫 번째 노드이자 마지막 노드가 되므로 포인터 front와 rear가 모두 새 노드를 가리키도록 설정한다.

3) 큐가 공백이 아닌 경우, 즉 노드가 있는 경우엔 현재 큐의 마지막 노드 다음에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정한다.

// 연결 큐의 rear에 원소를 삽입하는 연산
void enLQueue(LQueueType* LQ, element item) {
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = item;
    newNode->link = NULL;
    if (LQ->front == NULL) {                    // 현재 연결 큐가 공백 상태인 경우
        LQ->front = newNode;
        LQ->rear = newNode;
    }
    else {                                            // 현재 연결 큐가 공백 상태가 아닌 경우
        LQ->rear->link = newNode;
        LQ->rear = newNode;
    }
}

 

4. 연결 큐의 원소 삭제

큐가 공백이 아닌 경우에 수행한다.

 

1) 삭제할 노드는 큐의 첫 번째 노드로, 포인터 front가 가리키고 있는 노드이다. front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드로 지정한다.

2) 삭제 연산 후에는 현재 front 노드 다음 노드(front.link)가 front 노드가 되어야 하므로 포인터 front를 재설정한다.

3) 현재 큐에 노드가 하나뿐이어서 재설정한 front가 NULL이 되는 경우에는 삭제 연산 후에 공백 큐가 되므로 포인터 rear를 NULL로 설정한다.

4) 포인터 old가 가리키고 있는 노드를 삭제하여 메모리 공간을 시스템에 반환한다.

// 연결 큐에서 원소를 삭제하고 반환하는 연산
element deLQueue(LQueueType* LQ) {
    QNode* old = LQ->front;
    element item;
    if (isLQEmpty(LQ)) return;
    else {
        item = old->data;
        LQ->front = LQ->front->link;
        if (LQ->front == NULL)
            LQ->rear == NULL;
        free(old);
        return item;
    }
}

5. 연결 큐의 원소 검색

// 연결 큐에소 원소를 검색하는 연산element peekLQ(LQueueType* LQ) {
    element item;
    if (isLQEmpty(LQ)) return;
    else {
        item = LQ->front->data;
        return item;
    }
}

 

6. 연결 큐의 원소 출력

// 연결 큐의 원소를 출력하는 연산
void printLQ(LQueueType* LQ) {
    QNode* temp = LQ->front;
    printf(" Linked Queue : [");
    while (temp) {
        printf("%3c", temp->data);
        temp = temp->link;
    }
    printf(" ] ");
}

 

- 예제 : 연결 자료구조를 이용해 연결 큐 구현하기

#include "LinkedQueue.h"
 
int main(void) {
    LQueueType* LQ = createLinkedQueue();            // 연결 큐 생성
    element data;
    printf("\n ***** 연결 큐 연산 ***** \n");
    printf("\n 삽입 A>>"); enLQueue(LQ, 'A'); printLQ(LQ);
    printf("\n 삽입 B>>"); enLQueue(LQ, 'B'); printLQ(LQ);
    printf("\n 삽입 C>>"); enLQueue(LQ, 'C'); printLQ(LQ);
    data = peekLQ(LQ); printf(" peek item : %c \n", data);
    printf("\n 삭제 >>"); data = deLQueue(LQ); printLQ(LQ);
    printf("\t삭제 데이터 : %c", data);
    printf("\n 삭제 >>"); data = deLQueue(LQ); printLQ(LQ);
    printf("\t\t삭제 데이터 : %c", data);
    printf("\n 삭제 >>"); data = deLQueue(LQ); printLQ(LQ);
    printf("\t\t삭제 데이터 : %c", data);
    printf("\n 삽입 D>>"); enLQueue(LQ, 'D'); printLQ(LQ);
    printf("\n 삽입 E>>"); enLQueue(LQ, 'E'); printLQ(LQ);
    getchar(); return 0;
}