[7] 큐 ③ 연결리스트 ADT

연결리스트에 기초한 큐

단일연결리스트를 사용하여 큐를 구현할 수 있다.

 

☑ 삽입과 삭제가 특정위치에서만 수행되므로, 역방향링크는 불필요하다. (참고: 스택의 경우 헤더노드 불필요)

☑ front 원소를 연결리스트의 첫 노드에, rear 원소를 끝 노드에 저장하고 f와 r로 각각의 노드를 가리키게 한다.

 

• 기억장소 사용: O(n)
• 큐 ADT의 각 작업: O(1)

연결리스트 큐

헤더 및 구조체 선언

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

typedef char element;

#define MAX 10

typedef struct QueueNode {
    element data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    int size;
} QueueType;

이 코드는 연결 리스트를 이용하여 큐를 구현한다.

• QueueNode: 각 노드는 데이터를 담는 data 필드와 다음 노드를 가리키는 포인터인 next 필드로 구성됩니다.
• QueueType: front는 큐의 첫 번째 노드를 가리키는 포인터이고, rear는 큐의 마지막 노드를 가리키는 포인터이다. size는 큐의 현재 크기를 나타낸다.

연결 리스트를 사용하면 크기의 제한이 없어서 동적으로 메모리를 할당할 수 있고, 원소의 삽입과 삭제가 빠르게 이루 진다.

init 함수

void init(QueueType* Q) {
    Q->front = NULL;
    Q->rear = NULL;
    Q->size = 0;
}

 

이 함수는 큐를 초기화하는 역할을 한다.

• 큐의 첫 번째 노드를 가리키는 포인터인 front를 NULL로 초기화한다. 큐가 비어있음을 나타낸다.
• \큐의 마지막 노드를 가리키는 포인터인 rear를 NULL로 초기화한다. 큐가 비어있음을 나타낸다.
• \큐의 크기를 0으로 초기화한다. 현재 큐에 저장된 원소의 개수를 나타낸다.

따라서 이 함수를 호출하면 큐가 비어있는 상태로 초기화된다.

isEmpty 함수 / isFull 함수

int isEmpty(QueueType* Q) {return Q->size == 0;}

int isFull(QueueType* Q) {return Q->size >= MAX;}

이 두 함수는 각각 큐가 비어 있는지와 큐가 꽉 차 있는지를 확인한다.

 

• isEmpty: 큐가 비어있는지 확인한다. 만약 Q->size가 0이면 큐가 비어있는 상태이다.
• isFull: 큐가 꽉 차 있는지 확인한다. 만약 Q->size가 MAX와 같거나 크다면 큐가 꽉 찬 상태이다.

따라서 이 두 함수를 사용하여 큐의 상태를 확인할 수 있다.

enqueue 함수

void enqueue(QueueType* Q, element e) {
    QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));
    new->data = e;
    new->next = NULL;
    
    if (isEmpty(Q)) Q->front = new;
    else Q->rear->next = new;
    
    Q->rear = new;
    Q->size++;
}

 

이 함수는 큐에 원소를 삽입하는 역할을 한다.

 

1. 새로운 노드를 동적으로 할당하고, 해당 노드의 데이터 필드에 입력받은 원소를 저장한다.
2. 새로운 노드의 다음 노드를 NULL로 설정한다. 이 노드가 큐의 마지막 노드이므로 다음 노드는 없어야 한다.
3. 만약 큐가 비어있다면, front가 새로운 노드를 가리키도록 설정한다. 새로운 노드가 큐의 첫 번째 노드가 되므로 front와 rear가 모두 새로운 노드를 가리킨다.
4. 큐가 비어있지 않다면, 현재 rear가 가리키는 노드의 다음 노드로 새로운 노드를 연결한다.
5. rear를 새로운 노드로 업데이트한다. 이제 새로운 노드가 큐의 마지막 노드가 되므로 rear는 이를 가리켜야 한다.
6. 큐의 크기를 증가한다.

dequeue 함수

element dequeue(QueueType* Q) {
    if (isEmpty(Q)) {
        printf("Empty.\n");
        exit(EXIT_FAILURE);
    }
    
    QueueNode* del = Q->front;
    element val = del->data;
    
    Q->front = del->next;
    free(del);
    Q->size--;
    
    if (isEmpty(Q)) Q->rear = NULL;
    return val;
}

이 함수는 큐에서 원소를 삭제하는 역할을 한다.

 

1. 먼저 큐가 비어있는지 확인합니다. 만약 큐가 비어있다면 "Empty."를 출력하고 프로그램을 종료한다.
2. 큐의 첫 번째 노드인 Q->front를 가리키는 포인터인 del에 대한 포인터를 선언하고, 해당 노드의 데이터를 임시 변수 val에 저장한다.
3. Q->front를 del->next로 업데이트하여 큐에서 첫 번째 노드를 제거한다.
4. del이 가리키는 노드를 해제한다.
5. 큐의 크기를 감소시킨다.
6. 만약 큐가 비어있다면, rear를 NULL로 설정한다.
7. 삭제된 원소의 값을 반환한다.

이 함수를 통해 큐에서 원소를 삭제하며, 큐가 비어있는지 확인하여 언더플로우를 방지한다.

만약 큐가 비어있을 때 삭제를 시도한다면, 언더플로우 상황이 발생한다.

이 함수는 이러한 상황을 방지하기 위해 큐가 비어있는지를 먼저 확인하고, 비어있다면 오류 메시지를 출력하고 프로그램을 종료한다.

 

그 후에는 큐의 첫 번째 노드를 가리키는 포인터인 del을 생성하고, 해당 노드의 데이터를 임시 변수 val에 저장한다.

이후에는 큐의 front를 del->next로 업데이트하여 첫 번째 노드를 제거하고, del이 가리키는 노드를 해제한다.

그리고 큐의 크기를 하나 줄이고, 만약 큐가 이제 비어있다면 rear를 NULL로 설정한다.

 

마지막으로 삭제된 원소의 값을 반환한다.

print 함수

void print(QueueType* Q) {
    if (isEmpty(Q)) {
        printf("Empty.\n");
        return;
    }
    
    QueueNode* p = Q->front;
    
    while (p != NULL) {
        printf("[%c] ", p->data);
        p = p->next;
    }printf("\n");

}

이 함수는 큐에 저장된 모든 원소를 출력한다.

1. 먼저 큐가 비어있는지 확인합니다. 만약 큐가 비어있다면 "Empty."를 출력하고 함수를 종료한다.
2. 큐의 첫 번째 노드를 가리키는 포인터 p를 선언하고, 이를 Q->front로 초기화한다.
3. p가 NULL이 될 때까지 반복하면서, 각 노드의 데이터를 출력한다.
4. p를 다음 노드로 이동시킨다.
5. 모든 노드를 출력한 후에는 줄 바꿈 문자를 출력하여 출력이 한 줄에 하나씩 되도록 한다.

main 함수

int main() {
    QueueType Q; // 큐 선언
    Q.size = MAX; // 큐의 크기 설정
    init(&Q); // 큐 초기화

    srand(time(NULL));

    for (int i = 0; i < 7; i++) enqueue(&Q, rand()% 26 + 65);print(&Q);
    for (int i = 0; i < 3; i++) printf("[%c] is dequeded.\n",dequeue(&Q));print(&Q);
    
    for (int i = 0; i < 3; i++) enqueue(&Q, rand()% 26 + 65);print(&Q);
    for (int i = 0; i < 1; i++) printf("[%c] is dequeded.\n",dequeue(&Q));print(&Q);

    enqueue(&Q, rand()% 26 + 65);print(&Q);
}

전체 코드

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

typedef char element;

#define MAX 10

typedef struct QueueNode {
    element data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    int size;
} QueueType;

void init(QueueType* Q) {
    Q->front = NULL;
    Q->rear = NULL;
    Q->size = 0;
}

int isEmpty(QueueType* Q) {return Q->size == 0;}

int isFull(QueueType* Q) {return Q->size >= MAX;}

void enqueue(QueueType* Q, element e) {
    QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));
    new->data = e;
    new->next = NULL;
    
    if (isEmpty(Q)) Q->front = new;
    else Q->rear->next = new;
    
    Q->rear = new;
    Q->size++;
}

element dequeue(QueueType* Q) {
    if (isEmpty(Q)) {
        printf("Empty.\n");
        exit(EXIT_FAILURE);
    }
    
    QueueNode* del = Q->front;
    element val = del->data;
    
    Q->front = del->next;
    free(del);
    Q->size--;
    
    if (isEmpty(Q)) Q->rear = NULL;
    return val;
}

void print(QueueType* Q) {
    if (isEmpty(Q)) {
        printf("Empty.\n");
        return;
    }
    
    QueueNode* p = Q->front;
    
    while (p != NULL) {
        printf("[%c] ", p->data);
        p = p->next;
    }printf("\n");

}


int main() {
    QueueType Q; // 큐 선언
    Q.size = MAX; // 큐의 크기 설정
    init(&Q); // 큐 초기화

    srand(time(NULL));

    for (int i = 0; i < 7; i++) enqueue(&Q, rand()% 26 + 65);print(&Q);
    for (int i = 0; i < 3; i++) printf("[%c] is dequeded.\n",dequeue(&Q));print(&Q);
    
    for (int i = 0; i < 3; i++) enqueue(&Q, rand()% 26 + 65);print(&Q);
    for (int i = 0; i < 1; i++) printf("[%c] is dequeded.\n",dequeue(&Q));print(&Q);

    enqueue(&Q, rand()% 26 + 65);print(&Q);
}