큐 (Queue)

 

선입 선출(FIFO : First-In First-Out)을 기본으로 하는 자료 구조.

먼저 들어온 데이터가 먼저 나가고, 나중에 들어온 데이터가 나중에 나간다.

 

/*
    연결 리스트로 구현된 큐
    코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 
*/
#include <stdio.h>
#include <malloc.h>

typedef int element;
typedef struct QueueNode {
    element item;
    struct QueueNode *link;
} QueueNode;

typedef struct {
    QueueNode *front, *rear;
} QueueType;

void error(char * message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init(QueueType *q)
{
    q->front = q->rear = NULL;
}

int isEmpty(QueueType *q)
{
    return (q->front == NULL);
}

void push(QueueType *q, element item)
{
    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    
    if(temp == NULL) error("메모리를 할당할 수 없습니다.");
    else {
        temp->item = item;
        temp->link = NULL;
        
        if(isEmpty(q)) {
            q->front = temp;
            q->rear = temp;
        }
        else {
            q->rear->link = temp;
            q->rear = temp;
        }
    }
}

element pop(QueueType *q)
{
    QueueNode *temp = q->front;
    element item;
    
    if(isEmpty(q)) error("큐가 비어 있습니다");
    else {
        item = temp->item;
        q->front = q->front->link;
        
        if(q->front == NULL) q->rear = NULL;
        
        free(temp);
        return item;
    }
}

element peek(QueueType *q)
{
    if(isEmpty(q)) error("큐가 비어 있습니다");
    else return q->front->item;
}

void main() {
    QueueType q;
    init(&q);
    
    push(&q, 1);
    push(&q, 2);
    push(&q, 3);
    printf("pop() = %d\n", pop(&q));
    printf("pop() = %d\n", pop(&q));
    printf("pop() = %d\n", pop(&q));
}