연결리스트를 이용한 큐 구현(push, pop 함수)

큐

• 뒷쪽으로 들어가서 앞쪽으로 나오는 자료구조
• 먼저 들어간 게 먼저 나옴
• 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용
• 기본적인 형태의 자료구조

연결리스트로 큐 구현하기

큐 삽입함수(push)

• 새 노드를 마지막 노드 뒤에 넣고
• 새 노드의 next가 rear를 가리키게

typedef struct {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node    *front;
    Node    *rear;
    int     count;
} Queue;

void    push(Queue *queue, int data)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if (queue->count == 0)
    {
        queue->front = node;
    }
    else
    {
        queue->rear->next = node;
    }
    queue->rear = node;
    queue->count++;
}

큐 추출함수(pop)

• front가 front가 원래 가리켰던 node의 next를 가리키게 하고
• front가 원래 가리켰던 node 는 메모리 해제

int     pop(Queue *queue)
{
    if (queue->count == 0)
    {
        printf("queue underflow!\n");
        return (-1);
    }
    Node *node = queue->front;
    int data = node->data;
    queue->front = node->next;
    free(node);
    queue->count--;
    return (data);
}