Data-Structure - Queue

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_QUEUE_SIZE 100
#define ERROR_KEY -100

#define MALLOC(p, s)                            \
    if (!((p) = malloc(s)))                     \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

#define REALLOC(p, s)                           \
    if (!((p) = realloc(p, s)))                 \
    {                                           \
        fprintf(stderr, "Insufficient memory"); \
        exit(EXIT_FAILURE);                     \
    }

typedef struct
{
    int key;
} element;
element *queue;

int capacity = 1;
int rear = -1;
int front = -1;

void queueFull()
{
    REALLOC(queue, 2 * capacity * sizeof(*queue));
    capacity *= 2;
}

element queueEmpty()
{
    element errorElement;
    errorElement.key = ERROR_KEY;
    fprintf(stderr, "queue is empty, cannot delete element\n");
    return errorElement;
}

/* add an item to the queue */
void addq(element item)
{
    if (rear == MAX_QUEUE_SIZE - 1)
    {
        queueFull();
    }
    queue[++rear] = item;
}

/* remove element at the front of the queue */
element deleteq()
{
    if (front == rear)
        return queueEmpty();
    return queue[++front];
}

void deleteAndPrint()
{
    int key = deleteq().key;
    if (key != ERROR_KEY)
    {
        printf("%d\n", key);
        return;
    }
    return;
}

int main(void)
{
    MALLOC(queue, sizeof(*queue));
    element newElement = {1};
    addq(newElement);
    newElement.key = 3;
    addq(newElement);
    newElement.key = 2;
    addq(newElement);

    deleteAndPrint();
    deleteAndPrint();
    deleteAndPrint();
    deleteAndPrint();

    return 0;
}

간단히 c언어로 queue를 구현하였습니다. 

 

초기 queue의 용량을 1로 놓고 계속 꽉 찰 때마다 realloc해주어서 메모리 효율성을 높였습니다.

queue의 기본 작동방식은 queue[++rear]을 해서 값을 집어넣고 rear == MAX_QUEUE_SIZE - 1이 되어서 꽉 찼다는 것이고 realloc을 해줍니다. 그리고 데이터를 뺄 때는 FIFO정책에 따라 front값을 하나 더 만들어서 queue[++front]값을 return하고 만약에 front == rear라면 queue가 비었다는 것을 의미하므로 적절한 error 메세지를 띄워줍니다.

 

위의 코드에 대한 결과는 아래와 같습니다.

FIFO정책에 따라 queue의 값이 잘 빠져 나오는 것을 볼 수 있습니다.