Queue (C 언어)

C++ queue container 함수 정리 및

C queue 구현 예시

back은 가장 최근에 추가된 노드를 가리키고 있지만

front는 삭제할 노드가 아니라 삭제할 노드의 바로 앞을 가리키고 있음에 주의하자!!!

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

#define DEBUG 1
#define MAX_QUEUE_SIZE 10
#define MAX_INPUT_SIZE 20

//queue에 들어갈 data 구조체
typedef struct _Data {
    int xPos;
    int yPos;
} Data;

//queue 구조체
typedef struct _queue {
    Data mem[MAX_QUEUE_SIZE];
    int Front;
    int Back;
} queue;

bool empty(queue *);
void pop(queue *);
void push(queue *, Data *);
size_t size(queue *);
Data front(queue *);
Data back(queue *);
void initQueue(queue *);

int main(void)
{
    char inString[MAX_INPUT_SIZE];
    Data tempData;
    queue *qu = (queue *)malloc(sizeof(queue));
    initQueue(qu);

    printf("Program Start\n\n");
    printf("Input Order\n");
    printf("empty , pop , push , size , front , back , print , exit\n");
    while (1) {
        //input이 EOF 이거나 exit 이면 프로그램 종료
        if (scanf("%s", inString) == EOF || !strcmp("exit", inString)) {
            printf("Program End\n");
            break;
        }
        else if (!strcmp("empty", inString)) {
            if (empty(qu)) {
                printf("true\n");
            }
            else {
                printf("false\n");
            }
        }
        else if (!strcmp("pop", inString)) {
            pop(qu);
        }
        else if (!strcmp("push", inString)) {
            scanf("%d %d", &tempData.xPos, &tempData.yPos);
            push(qu, &tempData);
        }
        else if (!strcmp("size", inString)) {
            printf("%zd\n", size(qu));
        }
        else if (!strcmp("front", inString)) {
            tempData = front(qu);
            printf("(%d, %d)\n", tempData.xPos, tempData.yPos);
        }
        else if (!strcmp("back", inString)) {
            tempData = back(qu);
            printf("(%d, %d)\n", tempData.xPos, tempData.yPos);
        }
        else if (!strcmp("print", inString)) {
            for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
                printf("(%d, %d)\n", qu->mem[i].xPos, qu->mem[i].yPos);
            }
        }
        else {
            printf("invalid order\n");
        }
        printf("\nInput Order\n");
        printf("empty , pop , push , size , front , back , print , exit\n");
    }

    free(qu);
    return 0;
}

bool empty(queue *qu)
{
    if (qu->Front == qu->Back) { return true; }
    else { return false; }
}
void pop(queue *qu)
{
    if (empty(qu)) {
        printf("queue is empty\n");
        return;
    }
    qu->Front = (qu->Front + 1) % MAX_QUEUE_SIZE;
    qu->mem[qu->Front].xPos = -1;
    qu->mem[qu->Front].yPos = -1;
    return;
}
void push(queue *qu, Data *data)
{
    if ((qu->Back + 1) % MAX_QUEUE_SIZE == qu->Front) {
        printf("queue is full\n");
        return;
    }
    qu->Back = (qu->Back + 1) % MAX_QUEUE_SIZE;
    qu->mem[qu->Back].xPos = data->xPos;
    qu->mem[qu->Back].yPos = data->yPos;
    return;
}
size_t size(queue *qu)
{
    return (size_t)((qu->Back >= qu->Front) ? qu->Back - qu->Front : qu->Back - qu->Front + MAX_QUEUE_SIZE);
}
Data front(queue *qu)
{
    if (empty(qu)) {
        printf("queue is empty\n");
    }
    return qu->mem[(qu->Front + 1) % MAX_QUEUE_SIZE];
}
Data back(queue *qu)
{
    if (empty(qu)) {
        printf("queue is empty\n");
    }
    return qu->mem[qu->Back];
}
void initQueue(queue *qu)
{
    for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
        qu->mem[i].xPos = -1;
        qu->mem[i].yPos = -1;
    }
    qu->Front = MAX_QUEUE_SIZE - 1;
    qu->Back = MAX_QUEUE_SIZE - 1;

    return;
}