연결 리스트를 이용해서 큐를 구현하는것은, 연결 리스트를 이용해서 스택을 구현하는 것과 마찬가지로 배열을 이용해서 구현하는것 대비 많은 장점을 얻기 위해서이다.

연결 리스트로 큐를 구현하면 동적 할당의 성질에 의해서 메모리의 한계까지 큐의 크기를 늘릴 수도 있고, 동시에 큐가 아주 작을때에도 메모리를 조금밖에 차지하지 않는다.

일단 연결 리스트를 이용해서 큐를 구현할때에는 단순 연결 리스트(Simple Linked List)를 이용해서 구현하기에는 무리가 있다.

그 이유는 스택과 다르게 큐는 서로 다른 입구과 출구를 가지고 있기 때문인데, 단순 연결 리스트를 사용할 경우 get 동작은 머리 노드의 "뒷" 노드에서 자료를 가져오기 때문에 자연스러운 동작을 구현할 수 있다.

하지면 put 동작의 경우 꼬리 노드 "앞"에 새로운 노드를 삽입해야 하기 때문에 "앞(prev)" 노드를 가리키는 정보가 필요하게 된다.

따라서 앞 노드의 위치와 동시에 뒷 노드의 위치를 모두 알고있어야 해서 어쩔 수 없이 이중 연결 리스트(Double Linked List)로 구현을 해야한다.

물론 단순 연결 리스트를 이용해서 억지로 큐를 구현할수는 있지만 자연스러운것이 더 좋은법!!

---

큐 초기화

typedef struct _node {
    int key;
    struct _node *prev;
    struct _node *next;
} node;

node *head;
node *tail;

void init_queue(void) {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    
    head->prev = head;
    head->next = tail;
    tail->prev = head;
    tail->next = tail;
}

이중 연결 리스트를 이용해서 큐를 구현하기 위해서 첫번째로 2개의 링크를 갖는 노드구조와 head, tail 노드를 정의해야 한다.

다음으로 큐를 초기화할때 head, tail의 link를 조정해주면 된다.

---

Put

int put(int k) {
    node *new;
    
    if((new = (node *)malloc(sizeof(node))) == NULL) {
        printf("\nCould not put a value due to OOM\n");
        return -1;
    }
    
    // put into front of tail
    new->key = k;
    tail->prev->next = new;
    new->prev = tail->prev;
    tail->prev = new;
    new->next = tail;
    
    return k;
}

put 함수는 인자로 들어오는 k값을 가지는 노드를 새로 생성해 tail(꼬리) 노드 앞에 삽입해주면 된다.

배열과 다르게 연결 리스트를 이용해서 큐를 구현할 경우 미리 정해져있는 크기가 없기 때문에 자유롭지만, 메모리를 동적으로 할당받을때 Out Of Memory가 발생하지 않는지 확인해야한다.

또한 크게 어려운 부분은 없지만, 꼬리 앞쪽 부분으로 새로운 노드를 추가할때 링크 조작 순서에 신경을 써줘야 한다.

---

Get

int get(void) {
    node *temp;
    int key;
    
    temp = head->next;
    if(temp == tail) {
        printf("\nQueue underflow.\n");
        return -1;
    }
    
    key = temp->key;
    head->next = temp->next;
    temp->next->prev = head;
    free(temp);
    
    return key;
}

get 함수는 일단 큐가 비어있는지를 확인해야하는 절차가 필요하다.

큐가 비어있지 않으면 머리 바로 다음 노드를 삭제하면서 해당 노드의 값을 반환해주기만 하면 된다.

추가로 큐가 비어있는지를 확인하려면 간단하게 리스트의 초기 모습을 상상하면 되는데, head->next == tail 인지만 확인하면 된다.

---

Clear Queue

void clear_queue(void) {
    node *t;
    node *s;
    
    t = head->next;
    while(t != tail) {
        s = t;
        t = t->next;
        free(s);
    }
    
    head->next = tail;
    tail->prev = head;
}

마지막으로 큐를 초기화 하는 함수다.

사실 연결 리스트이기 때문에 단순히 init_queue에서 했던것 처럼 head와 tail 노드의 링크만 재조정해줘도 될것 같지만 안된다.

단순히 아래와 같이 head와 tail node의 link만 재조정 할경우에는 head와 tail사이에 저장된 데이터, 즉 queue에 저장된 데이터들의 memory가 반환되지 않게된다.

따라서 이는 memory leak을 야기하고 queue의 크기가 작은 상태에서는 티가 나지 않을 수 있지만, queue의 크기가 큰 상태에서는 꽤나 큰 성능 문제를 일으킬 수 있으므로 조심하고 신경써야한다.

head->next = tail;
tail->prev = head;

따라서 Queue를 초기화 할때에는 반드시 head와 tail 사이에 위치한 node들의 memory를 반환시켜줘야 한다.

---

전체 코드

//
//  main.c
//  Queue_LinkedLIst
//
//  Created by 박재현 on 2024/05/11.
//


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

typedef struct _node {
    int key;
    struct _node *prev;
    struct _node *next;
} node;

node *head;
node *tail;

void init_queue(void) {
    head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    
    head->prev = head;
    head->next = tail;
    tail->prev = head;
    tail->next = tail;
}

int put(int k) {
    node *new;
    
    if((new = (node *)malloc(sizeof(node))) == NULL) {
        printf("\nCould not put a value due to OOM\n");
        return -1;
    }
    
    // put into front of tail
    new->key = k;
    tail->prev->next = new;
    new->prev = tail->prev;
    tail->prev = new;
    new->next = tail;
    
    return k;
}

int get(void) {
    node *temp;
    int key;
    
    temp = head->next;
    if(temp == tail) {
        printf("\nQueue underflow.\n");
        return -1;
    }
    
    key = temp->key;
    head->next = temp->next;
    temp->next->prev = head;
    free(temp);
    
    return key;
}

void clear_queue(void) {
    node *t;
    node *s;
    
    t = head->next;
    while(t != tail) {
        s = t;
        t = t->next;
        free(s);
    }
    
    head->next = tail;
    tail->prev = head;
}

void print_queue(void) {
    node *t;
    t = head->next;
    
    while(t != tail) {
        printf("%-6d", t->key);
        t = t->next;
    }
    printf("\n");
}

int main(int argc, const char * argv[]) {
    int i;
    
    init_queue();
    
    printf("Put 5, 4, 7, 8, 2, 1\n");
    put(5);
    put(4);
    put(7);
    put(8);
    put(2);
    put(1);
    print_queue();
    
    printf("\nGet\n");
    i = get();
    print_queue();
    printf("Getting value is %d\n", i);
    
    printf("\nPut 3, 2, 5, 7\n");
    put(3);
    put(2);
    put(5);
    put(7);
    print_queue();
    
    printf("\nPut 3\n");
    put(3);
    print_queue();
    
    printf("\nInitialize Queue\n");
    clear_queue();
    print_queue();
    
    printf("\nCurrently queue is empty.\n");
    i = get();
    print_queue();
    printf("\nGetting value is %d\n", i);
    
    return 0;
}

실행 결과