[C언어와 함께 자료구조를] 연결리스트로 큐 구현하기

큐 개념 다시 보기

큐는 줄, 대기행렬 이라는 의미가 있습니다. 줄서서 먹는 맛집은 온 순서대로 들어가게 되는 것과 같은 개념이라고 생각하시면 됩니다. 큐를 대표하는 말은 선입선출( FIFO : First In First Out)인데요, 거꾸로 생각하면 후입후출(LILO : Last In Last Out)도 틀린 말은 아닌 것 같습니다. 

큐의 연산도 딱 두가지 put과 get입니다. 뭐 책에 따라서 enqueue, dequeue라는 말도 쓰이긴 하지만 의미만 통하면 별 문제는 없어 보입니다. put은 큐에 데이터를 넣는것, get은 큐에서 데이터를 가져오는 것입니다. 

 

연결리스트로 큐 구현하기

배열을 이용한 큐에서는 큐의 크기가 정해져 있었지만, 연결리스트에서는 그런 제약조건이 없습니다. (이론상 컴이 더이상 메모리 할당을 못할 때까지 큐의 크기가 커집니다.)

우선 연결리스트를 정의하고, front와 rear 노드를 선언하겠습니다.

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

node *front, *rear;
node *data;

다음으로 큐를 초기화하는 함수를 만들겠습니다. 초기화는 front와 rear노드의 메모리를 할당하고 연결리스트를 초기화하는 역할을 합니다.

void init_queue ()
{
    front = (node *)malloc(sizeof(node));
    rear = (node *)malloc(sizeof(node));
    front->next = rear;
    rear->next = rear;
}

다음으로 put연산을 아래와 같이 정의 합니다. 새로운 노드의 메모리를 할당하여 rear 노드의 앞에 삽입합니다. put연산에서 if문의 큐 생성 초기 데이터 노드가 없는 경우, 기존 데이터 노드가 있는 경우로 나눠서 생각을 했는데요. 데이터 노드가 있는 경우 rear가 바로 앞의 노드를 가리키지만, 없는 경우 자신을 가리키기 때문에 바로 앞노드를 찾을 수 없기 때문입니다.

 

void put (int val)
{
    data = (node *)malloc(sizeof(node));
    data->key = val;
    
    if (front->next == rear) {
        front->next = data;
        data->next = rear;
        rear->next = data;
    } else {
        rear->next->next = data;
        data->next = rear;
        rear->next = data;
    }
}

다음은 put연산은 rear노드의 앞에 데이터노드를 삽입했는데요. get연산은 front노드의 다음 데이터 노드를 가져오는 역할을 합니다. 코드를 보면 아래와 같습니다. front가 rear를 가리키는 경우 큐가 비어있는 상태이므로 체크해주고 front노드의 다음노드를 삭제하는 연결리스트의 연산을 수행해 줬습니다.

int get ()
{
    int key;
    node *data;
    
    if (front->next == rear) {
        printf(" Queue Underflow");
        return -1;
    }
    
    data = front->next;
    front->next = data->data;
    key = data->key;
    
    free (data);
    
    return key;
}

연결리스트의 개념을 이해했다면, 충분히 구현이 가능한 내용입니다. 다음은 전체 소스와 실행 결과를 보겠습니다.

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


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

node *front, *rear;
node *data;

void init_queue ()
{
    front = (node *)malloc(sizeof(node));
    rear = (node *)malloc(sizeof(node));
    front->next = rear;
    rear->next = rear;
}

void put (int val)
{
    data = (node *)malloc(sizeof(node));
    data->key = val;
    
    if (front->next == rear) {
        front->next = data;
        data->next = rear;
        rear->next = data;
    } else {
        rear->next->next = data;
        data->next = rear;
        rear->next = data;
    }
}

int get ()
{
    int key;
    node *data;
    
    if (front->next == rear) {
        printf(" Queue Underflow");
        return -1;
    }
    
    data = front->next;
    front->next = data->next;
    key = data->key;
    
    free (data);
    
    return key;
}

void print_queue ()
{
    node *sp;
    printf ("\n Queue From Front-----> To Rear\n");

    for (sp = front->next; sp != rear; sp = sp->next)
        printf("%-6d", sp->key);
}

void main ()
{
    int i;
    init_queue ();

    printf (" Put 5, 4, 7, 8, 2, 1");
    put(5);
    put(4);
    put(7);
    put(8);
    put(2);
    put(1);
    print_queue();
  

    printf("\n Get");
    i = get();
    print_queue();
    printf("\n    get value is %d\n", i);

    printf(" Put 3, 2, 5, 7\n");
    put(3);
    put(2);
    put(5);
    put(7);
    print_queue();
   
   
    printf("\n Initialize Queue");
    init_queue();
    print_queue();

   

    printf(" Now queue is empty, get\n");
    i = get();
    print_queue();
    printf("    get value is %d", i);

}

다음은 실행결과 입니다.

PS C:\CS> .\linkedlist_queue.exe
 Put 5, 4, 7, 8, 2, 1
 Queue From Front-----> To Rear
5     4     7     8     2     1
 Get
 Queue From Front-----> To Rear
4     7     8     2     1
    get value is 5
 Put 3, 2, 5, 7

 Queue From Front-----> To Rear
4     7     8     2     1     3     2     5     7
 Initialize Queue
 Queue From Front-----> To Rear
 Now queue is empty, get
 Queue Underflow
 Queue From Front-----> To Rear
    get value is -1

별로 어렵지 않았죠? 기본자료형의 개념이 간단하다고 간단히 넘어가시면 안되구요. 간단한 만큼 활용도가 매우 높다는 사실을 기억하시길 바랍니다. 그럼 안녕~