[ch 07-3] 큐의 연결 리스트 기반 구현(구현)

[연결 리스트 기반 스택과 큐의 차이점]

- 스택은 'push'와 'pop'이 같은 위치에서 처리가 되는 반면, 큐는 'enqueue'와 'dequeue'가 다른 위치에서 처리가 됨

[소스 코딩]

■ ListBaseQueue.h

#ifndef LISTBASEQUEUE_H_
#define LISTBASEQUEUE_H_
 
#define TRUE    1
#define FALSE    0
 
typedef struct _node
{
    int 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, int data);  // 큐에 데이터를 저장하는 함수
int Dequeue(Queue * pq);             // 큐의 데이터를 반환하는 함수
int QPeek(Queue * pq);               // 큐의 데이터를 조회하는 함수
 
#endif

■ ListBaseQueue.c

#include <stdio.h>
#include <stdlib.h>            // malloc, free 함수를 사용하기 위함
#include "ListBaseQueue.h"
 
// 큐 초기화 함수 //
void QueueInit(Queue * pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}
 
// 큐에 데이터가 존재하는지 확인하는 함수 //
int QIsEmpty(Queue * pq)
{
    if(pq->front == NULL)
        return TRUE;
 
    else
        return FALSE;
}
 
// 큐에 데이터를 저장하는 함수 //
void Enqueue(Queue * pq, int 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;
        pq->rear = newNode;
    }
}
 
// 큐의 데이터를 반환하는 함수 //
int Dequeue(Queue * pq)
{
    Node * delNode;
    int retData;
 
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Empty!!");
        exit(-1);
    }
 
    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;
 
    free(delNode);
    return retData;
}
 
// 큐의 데이터를 조회하는 함수 //
int QPeek(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Empty!!");
        exit(-1);
    }
 
    return pq->front->data;
}

■ 사용되는 함수 설명

void QueueInit(Queue * pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}

- 노드를 가리킬 'front'와 'rear'를 'NULL'로 초기화

int QIsEmpty(Queue * pq)
{
    if(pq->front == NULL)
        return TRUE;
 
    else
        return FALSE;
}

// 'front'가 'NULL'을 가리킬 경우

- 'TRUE'를 반환

// 아닐 경우

- 'FALSE'를 반환

void Enqueue(Queue * pq, int 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;
        pq->rear = newNode;
    }
}

- 새로운 노드(newNode)를 생성(동적 메모리 할당)

- 새로운 노드는 항상 끝을 의미하기 위해 'next'를 'NULL'로 초기화

- 새로운 노드에 사용자에게 입력 받은 'data'를 저장

// 큐에 데이터가 비워져 있을 경우('front'가 'NULL'을 가리킴)

- 'front'와 'rear'는 생성된 노드(newNode)를 가리킴

// 큐에 데이터가 존재할 경우

- 'rear'가 가리키던 기존 노드는 새로운 노드를 가리킴

  ※ 가장 최근에 생성된 노드가 새로운 노드를 가리킴

- 'rear'는 생성된 노드를 가리킴으로써 위치 이동

※ enqueue 처리 과정

int Dequeue(Queue * pq)
{
    Node * delNode;
    int retData;
 
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Empty!!");
        exit(-1);
    }
 
    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;
 
    free(delNode);
    return retData;
}

- 삭제할 노드를 저장할 'delNode' 선언

- 반환할 노드의 값을 저장할 'retData' 선언

// 큐에 데이터가 비워져 있을 경우('front'가 'NULL'을 가리킴)

- 큐에 데이터가 존재하지 않다는 메시지 출력 후 프로그램 종료

// 큐에 데이터가 존재할 경우

- 'front'가 가리키던 노드를 'delNode'에 저장

- 'delNode'에 저장된 data를 'retData'에 저장

- 'front'는 삭제될 노드의 다음 노드를 가리킴

- 'delNode'를 삭제하고, 저장되었던 값을 반환

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

// 큐에 데이터가 비워져 있을 경우('front'가 'NULL'을 가리킴)

- 큐에 데이터가 존재하지 않다는 메시지 출력 후 프로그램 종료

// 큐에 데이터가 존재할 경우

- 'front'가 가리키던 노드의 값을 반환

※ dequeue 처리 과정

■ ListBaseQueueMain.c

#include <stdio.h>
#include "ListBaseQueue.h"
 
int main(void)
{
    Queue Q;
    QueueInit(&Q);
 
    Enqueue(&Q, 11);    Enqueue(&Q, 22);
    Enqueue(&Q, 33);    Enqueue(&Q, 44);
 
    while(!QIsEmpty(&Q))
        printf("%d ", Dequeue(&Q));
 
    return 0;
}

- 연결 리스트 기반 구조체 'Q' 선언 및 초기화

- 데이터 저장(11 → 22 → 33 → 44)

- Q에 데이터가 비워질 때까지 존재하는 데이터를 순서대로 출력

■ 실행결과