Programming/C, C++

[C/C++]연결 큐(Linked Queue)

MB Brad KWON 2012. 10. 14. 22:28


LinkedQueue.h




 큐는 자료구조에서 없어서는 안 된다. 큐는 FIFO(First In First Out), 선입선출 구조를 가진 자료구조로 여러군데서 이용이 가능하다. 기수 정렬에서도 사용되고 프로세스 스케줄링과 같은 곳에서도 사용이 된다. 그리고 기타 여러 선입선출 방식을 취할 때 사용된다. 이 코드는 링크를 이용한 큐이다. 


1. LinkedQueue.h



#include <malloc/malloc.h>


// 노드

typedef struct QueueNode{

    int item;

    struct QueueNode *link;

} QueueNode;


// 타입

typedef struct{

    QueueNode *front, *rear;

} QueueType;


//에러 처리 함수

void error(char *message)

{

    fprintf(stderr, "%s\n", message);

    exit(1);

}


//초기화 함수

void initQueue(QueueType *q)

{

    q->front = q->rear = 0;

}


//공백상태 검사

int isEmpty(QueueType * q)

{

    return (q->front==NULL);

}


//포화상태 검사

int isFull(QueueType *q)

{

    return 0;

}


//삽입함수

void enqueue(QueueType *q, int item)

{

    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));

    

    if(temp == NULL)

    {

        error("memory allocation is failed\n");

    }

    

    else

    {

        temp->item = item;

        temp->link = NULL;

        if(isEmpty(q))

        {

            q->front = temp;

            q->rear = temp;

        }

        

        else

        {

            q->rear->link = temp;

            q->rear = temp;

        }

    }

}


//삭제함수

int dequeue(QueueType *q)

{

    QueueNode *temp = q->front;

    int item;

    

    if(isEmpty(q))

    {

        error("queue is empty\n");

    }

    

    else

    {

        item = temp->item;

        q->front = q->front->link;

        

        if(q->front == NULL)

            q->rear = NULL;

        

        free(temp);

        return item;

    }

}


//peek 함수

int peek(QueueType *q)

{

    if(isEmpty(q))

        error("queue is empty\n");

    else

    {

        int item = q->front->item;

        return item;

    }

}