[C] 이중 연결 리스트(Doubly Linked List)를 이용한 큐(Queue) 구현

큐란, 먼저 들어온 데이터가 먼저 나가는, 선입선출, FIFO(First in First out)구조를 가진다.

출처: https://cocoon1787.tistory.com/691

 

큐(queue)는, 영어단어인 queue라는 단어의 뜻에서도 이러한 의미를 가지는데, 대기 행렬, 줄이라는 뜻을 가진다. 먼저 줄선 사람이 먼저 나가듯이, queue라는 뜻 자체가 선입선출의 의미를 갖는다고 볼 수 있다.

 

저번에 스택을 구현할 때는 동적 할당으로 길이를 늘리는 배열처럼 사용하여 데이터를 배열에 순차적으로 입력하면서 처리하면 되었지만, 큐는 그런 방식으로 해결을 볼 수 없었다. 배열을 사용하면, 데이터를 앞에서부터 뒤로 순차적으로 입력하면, pop을 수행할 때마다 데이터가 배열 중간에 위치하게 되는데, 이때 데이터들을 앞으로 한칸씩 복사하면서 값을 갱신하는데, 이 때 배열 내부를 전부(정확히는 들어있는 데이터의 개수만큼) 돌아야 하기 때문에 O(n)의 시간복잡도를 가지게 되는데, 필자는 최대한 O(1)로 처리하고 싶었다. 그래서 떠올린 방법이 연결 리스트였다. 그러다가, 이번에도 pop에서 걸렸다. 데이터를 제거하려면 맨 끝으로 이동하게 되는데, 이때에도 시간복잡도가 O(n)이 되어버리는 것이다. 그래서 맨 마지막 노드를 가르킬 포인터를 사용해봤지만, 단일 연결 리스트로 처리하려다 보니, 맨 마지막 노드의 바로 이전 노드가 가르키는 포인터를 수정할 방법이 없었다(NULL을 가르키게 해야하니까). 그래서 떠올린 것이 이중 연결 리스트였다. 그냥 단일 연결 리스트에서 사용하는 노드에 이전 노드를 가르킬 포인터를 하나 더 추가한 것 뿐이다.

 

그러면 큐를 구현해보자. 이번에 큐를 동작시키기 위해 구현할 함수는 총 7가지로, 다음과 같다.

• 스택을 초기화할 init_queue
• 데이터를 추가할 push
• 제일 앞의 데이터를 제거할 pop 
• 제일 앞의 데이터, 그러니까 제일 먼저 들어온 데이터를 반환할 front
• 제일 마지막 데이터, 그러니까 제일 늦게 들어온 데이터를 반환할 back
• 데이터가 얼마나 담겨있는지 알아낼 size
• 큐가 비었는지 체크할 empty

 

일단 연결 리스트를 사용하기 때문에 노드부터 만들어 주자.

 

typedef struct _node{
    struct _node* _prev; // 이전 노드를 가르키는 포인터
    int _data; // 데이터
    struct _node* _next; // 다음 노드를 가르키는 포인터
}node;

 

이제 노드를 이용해서 큐 구조체를 만들자.

 

typedef struct _queue{ 
    node* _list; // 실제 데이터를 담는 포인터
    node* _front; // 맨 앞 노드를 가르키는 포인터
    int _len;
}queue;

 

_list가 이중 연결 리스트이고. _front는 단순히 맨 앞 노드를 가르키기만 한다.

1. init_queue

큐를 초기화하는 init_queue함수를 구현해보자.

 

queue* init_queue(){
    queue* ret = (queue* )malloc(sizeof(queue));
    // 아무 것도 없기 때문에 null값 할당
    ret->_list = NULL;
    ret->_front = NULL;
    ret->_len = 0;
    return ret;
}

 

저번에 스택에서는 _top을 이용해 길이와 동적 할당한 배열의 인덱스로 모두 사용하기 위해 초기값을 -1로 하여 길이와 1만큼 차이가 있었지만, 이번에는 인덱스를 조회하기 위한 용도가 아니기 때문에 바로 길이값으로 사용하도록 했다.

2. push

데이터를 추가하는 push함수를 구현해보자.

 

맨 처음에는 큐의 모든 포인터가 NULL을 가르킬 것이다. 그렇게 만들었으니까. 이제 3을 push해보자.

내 그림

맨 처음에 추가할 때에는 생성한 노드 하나밖에 없기 때문에 _prev와 next가 모두 NULL을 가르키게 한다. _prev를 NULL로 설정하는 이유는 이상한 영역을 가르키게 하지 않기 위해서이다. _next를 NULL로 가르킨 이유는 끝 노드임을 나타내기 위해서이다.

 

하지만 노드가 두개 이상이 되면 조금 더 수행해야할 일이 있다. 7을 push한다고 가정하고 다음을 보자.

내 그림

바로 앞 노드인 3노드의 prev가 새로 push된 7노드를 가르키게 하는 작업을 거쳐야 한다.

 

이를 코드로 구현해보자.

 

void push(queue* q, int data){
    // new node
    node* new_node = (node* )malloc(sizeof(node));
    new_node->_data = data;
    new_node->_next = q->_list; // q->_list가 곧 new_node가 다음으로 가르켜야 할 노드이다
    new_node->_prev = NULL;

    ++q->_len; // 길이 1 증가
    if(q->_len == 1) { // 길이가 1 -> 노드가 하나밖에 없기 때문에, front를 설정한다.
        q->_front = new_node;
    }
    else { // 기존의 q->_list가 이전노드로 new_node를 가르키도록 한다.
        q->_list->_prev = new_node;
    }
    q->_list = new_node; // q->_list에 추가
}

3. pop

맨 앞의 데이터를 제거하는 pop함수를 구현해보자.

 

노드가 2개 이상인 현재의 상황을 보자.

내 그림

일단 _front가 가리키는 노드를 없애야 하기 때문에 _front노드가 가르키는 노드의 _prev를 통해 이전 노드를 가리키도록 한다. 이렇게 가리키게 된 front노드는 맨 끝 노드가 되어버렸으므로 _next가 NULL을 가르키도록 한다. 그리고 길이를 줄인 후에 할당을 해제 한다.

 

노드가 한개일때는 조금 다른 작업을 수행한다.

노드가 한개일 때는, 노드의 수정 없이 큐의 포인터 변수인 _list와 _front를 모두 NULL을 가리키게 하여 초기값으로 다시 설정한다.

 

이를 코드로 구현해보자.

 

void pop(queue* q){
    if (q->_len){ // pop할 노드가 있다면
        node* del = q->_front; // 맨 끝 노드를 가리킨다.
        q->_front = q->_front->_prev; // front를 바로 뒤의 노드를 가리키도록 수정한다.
        if(q->_len >= 2) { // 노드가 2개 이상이라면
            q->_front->_next = NULL; // 수정한 front노드의 next가 NULL을 가리키도록 한다.
        }
        else { // 노드가 1개라면
            q->_list = NULL; // 초기값으로 다시 설정
        }
        --q->_len;
        free(del); // 할당 해제
    }
    else return;
}

 

4. front

큐 내부의 _front를 통해 반환한다. 만약 큐가 비어있으면 -1을 반환한다.

 

int front(queue* q){
    if (q->_len){
        return q->_front->_data;
    }
    else return -1;
}

 

5. back

큐 내부의 _list를 통해 반환한다. 역시 비어있다면 -1을 반환한다.

 

int back(queue* q){
    if (q->_len){
        return q->_list->_data;
    }
    else return -1;
}

 

6. size

큐 내부의 _len을 반환한다.

 

int size(queue* q){
    return q->_len;
}

 

7. empty

큐 내부의 _len이 0인지 비교한 값을 반환한다.

 

int empty(queue* q){
    return q->_len == 0;
}

전체 코드

#include <stdlib.h>

// implement using dynamic allocation
typedef struct _node{
    struct _node* _prev; // 앞 노드를 가르키는 포인터
    int _data; // 데이터
    struct _node* _next; // 다음 노드를 가르키는 포인터
}node;

typedef struct _queue{ 
    node* _list; // 실제 데이터를 담는 포인터
    node* _front; // 맨 앞 노드를 가르키는 포인터
    int _len;
}queue;

queue* init_queue(){
    queue* ret = (queue* )malloc(sizeof(queue));
    // 아무 것도 없기 때문에 null값 할당
    ret->_list = NULL;
    ret->_front = NULL;
    ret->_len = 0;
    return ret;
}

void push(queue* q, int data){
    // new node
    node* new_node = (node* )malloc(sizeof(node));
    new_node->_data = data;
    new_node->_next = q->_list; // q->_list가 곧 new_node가 다음으로 가르켜야 할 노드이다
    new_node->_prev = NULL;

    ++q->_len; // 길이 1 증가
    if(q->_len == 1) { // 길이가 1 -> 노드가 하나밖에 없기 때문에, rear를 설정한다.
        q->_front = new_node;
    }
    else { // 기존의 q->_list가 이전노드로 new_node를 가르키도록 한다.
        q->_list->_prev = new_node;
    }
    q->_list = new_node; // q->_list에 추가
}

void pop(queue* q){
    if (q->_len){ // pop할 노드가 있다면
        node* del = q->_front; // 맨 끝 노드를 가리킨다.
        q->_front = q->_front->_prev; // front를 바로 뒤의 노드를 가리키도록 수정한다.
        if(q->_len >= 2) { // 노드가 2개 이상이라면
            q->_front->_next = NULL; // 수정한 front노드의 next가 NULL을 가리키도록 한다.
        }
        else { // 노드가 1개라면
            q->_list = NULL; // 초기값으로 다시 설정
        }
        --q->_len;
        free(del); // 할당 해제
    }
    else return;
}

int front(queue* q){
    if (q->_len){
        return q->_front->_data;
    }
    else return -1;
}

int back(queue* q){
    if (q->_len){
        return q->_list->_data;
    }
    else return -1;
}

int size(queue* q){
    return q->_len;
}

int empty(queue* q){
    return q->_len == 0;
}

테스트

큐를 구현했으니, 테스트를 해보자. 저번에 스택을 구현할때와 마찬가지로, 그냥 "queue.c"라고 저장하고 include해서 사용하겠다. 이유는 역시나 귀차니즘....

 

#include <stdio.h>
#include "queue.c"

void print_queue(queue* q){
    printf("back -> front : ");
    node* temp = q->_list;
    for (int i = 0; i < q->_len; i++) {
        printf("%d ", temp->_data);
        temp = temp->_next;
    }
    printf("\n");

    printf("front -> back : ");
    temp = q->_front;
    for (int i = 0; i < q->_len; i++) {
        printf("%d ", temp->_data);
        temp = temp->_prev;
    }
    printf("\n");
}

void stat(queue* q){
    printf("front -> %d\n", front(q));
    printf("back -> %d\n", back(q));
    printf("size -> %d\n", size(q));
    printf("is empty? -> %s\n", empty(q) ? "true" : "false");
}

int main(){
    queue* q = init_queue();
    printf("is empty? -> %s\n", empty(q) ? "true" : "false");

    for(int i = 5; i > 0; i--) {
        push(q, i);
    }
    print_queue(q);
    stat(q);

    printf("----------------------\n");
    for (int i = 0; i < 4; i++) {
        pop(q);
        print_queue(q);
        stat(q);
        printf("\n");
    }
    pop(q);
    print_queue(q);
    stat(q);
}

 

활용

그렇다면 큐는 어디에 사용할까?

 

우선 게임좀 하는 사람들은 이런말을 많이 해봤을 것이다. "아~ 큐 왜이렇게 안잡혀~" 여기서 말하는 큐가 매칭을 시작한 시간에 따라 큐에 들어간 것이다.

 

또한 프린터의 출력 순서에도 큐를 사용한다. 출력을 요청한 순서에 따라 순차적으로 처리하기 위해서이다.

 

이렇듯 큐는 순차적인 데이터를 처리하기 위해 사용한다.

느낀 점

필자는 자료구조에 관한 글을 포스팅하면서 단일 연결 리스트만 구현하고 이중 연결 리스트를 구현하지는 않았다. 그냥 노드에 이전 노드를 가르킬 포인터만 추가하고, 이를 수정하는 과정만 추가하면 되기 때문에, 굳이 구현해야할 필요성을 느끼지 못했기 때문이다. 그래서 이번에 큐를 구현하는게, 큐와 이중 연결 리스트를 동시에 공부하게 되어 상당히 보람찼다.

 

그리고 이번에 처음으로 왜 사람들이 포인터를 싫어하는지 이해가 갈 정도로 초반에 구현하는데 상당히 복잡해서 코드를 여러번 갈아엎었다. 누가 누굴 가르키고 있는건지~ 내가 수정하고 있는게 제대로 수정하고 있는건 맞는지~ 정말 복잡했다. 그래도 완성해서 매우 기분이 좋다.