Chap07. 큐, 연결 리스트 기반의 큐

연결 리스트 기반의 큐 구현 

연결 리스트 기반의 큐는 배열 기반의 원형 큐와 달리 고려해야할 점이 좀 줄어든다.



연결 리스트 기반의 큐의 Enqueue

Enqueue 시에는 두가지 경우로 나뉜다.

1. 첫 번째 노드를 삽입하는 경우 

- F,R 모두 새 노드를 가르킨다 

 

2. 두 번쨰 이후 노드를 삽입하는 경우

- F는 그대로, R은 새 노드를 가르킨다 

- 노드 간의 연결을 위해 가장 끝에 있는 노드가 새 노드를 가르킨다 

 

연결 리스트 기반의 큐의 Dequeue 

Dequeue의 경우 Enqueue와 달리 경우가 나뉘지 않는다.

- F가 다음 노드를 가르키게 한다.

- F가 이전에 가르키던 노드를 소멸시킨다.

 

이렇게 할 경우 F와 R이 같은 노드를 가르킬때, Dequeue 연산을 하면 F는 NULL값을 가르키고, R은 아무것도 아닌 쓰래기값을 가르키게 된다. 하지만 R이 쓰래기값을 가르켜도 상관이 없다. 왜냐면 큐가 비어있는지 확인할때에도 F가 NULL인지만 확인하고 다른 어떤 연산에서도 R의 값을 참조하는 경우가 없기 때문이다. 

 

---

ListBaseQueue.h

/*
 * 연결 리스트 기반 큐 구현
 */

#ifndef CHAP07_LISTBASEQUEUE_LISTBASEQUEUE_H
#define CHAP07_LISTBASEQUEUE_LISTBASEQUEUE_H

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
    Data data;
    struct _node *next;
} Node;

typedef struct _lQueue
{
    Node *front;
    Node *rear;
} LQueue;

typedef LQueue Queue;

void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);

void Enqueue(Queue *pq, Data data);
Data Dequeue(Queue *pq);
Data QPeek(Queue *pq);

#endif //CHAP07_LISTBASEQUEUE_LISTBASEQUEUE_H

ListBaseQueue.c

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

// 최초에 front, rear 모두 NULL을 가르킴
void QueueInit(Queue *pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}

// front의 위치만으로 큐가 비었는지 판단함
int QIsEmpty(Queue *pq)
{
    if(pq->front == NULL) return TRUE;
    else return FALSE;
}

void Enqueue(Queue *pq, Data data)
{
    Node *newNode = (Node*)malloc(sizeof(Node*));
    newNode->next = NULL;
    newNode->data = data;

    // 첫 번째 노드 삽입 시
    if(QIsEmpty(pq))
    {
        pq->front = newNode;
        pq->rear = newNode;
    }
    //
    else
    {
        // 마지막 노드가 새 노드 가르키도록
        pq->rear->next = newNode;
        // rear가 새 노드 가르키도록
        pq->rear = newNode;
    }
}

Data Dequeue(Queue *pq)
{
    Node *delNode;
    Data retData;

    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error");
        exit(-1);
    }

    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;

    free(delNode);
    return retData;
}

Data QPeek(Queue *pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error");
        exit(-1);
    }
    return pq->front->data;
}

ListBaseQueueMain.c

#include <stdio.h>
#include "ListBaseQueue.h"

int main()
{
    Queue q;
    QueueInit(&q);

    // Data Enqueue
    Enqueue(&q, 1);
    Enqueue(&q, 2);
    Enqueue(&q, 3);
    Enqueue(&q, 4);
    Enqueue(&q, 5);

    // Data Dequeue
    while(!QIsEmpty(&q))
    {
        printf("%d ", Dequeue(&q));
    }
}