[자료구조론/C] 자료구조론 4편 큐

큐

선입선출 자료구조이다. C++ 덱 컨테이너의 하위호환으로 생각하면 되려나.

큐의 ADT

enqueue와 dequeue이 두 가지가 핵심. 자료구조를 처음 가르쳐주셨던 교수님의 성함을 이니셜로 따면 디큐였는데 디큐 디큐 할 때마다 그분이 떠오른다. 아무튼 c로 구현하자면

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

정도가 되겠다.

연결리스트 기반의 큐 구현

• 헤더 파일

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__
#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
    struct _node * next;
    Data data;
} 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);

• 메서드 구현한 c 파일

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

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

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

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

    if(QIsEmpty(pq)) {
        pq->front = newNode;
        pq->rear = newNode;
    }

    else {
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}

Data Dequeue(Queue *pq)
{
    Node *rnode;
    Data rdata;

    if(QIsEmpty(pq)) {
        printf("Queue is empty");
        exit(-1);
    }

    rnode = pq->front;
    rdata = pq->front->data;

    pq->front = pq->front->next;
    free(rnode);

    return rdata;
}

Data QPeek(Queue *pq)
{
    if(QIsEmpty(pq)) {
        printf("Queue is empty");
        exit(-1);
    }

    return pq->front->data;
}

• main 파일

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

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

    Enqueue(&q, 1);
    Enqueue(&q, 2);
    Enqueue(&q, 3);

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

    return 0;
}

결과는 1 2 3일 것이다.

끝