C 큐(Queue) 구현

큐

- 선형 자료구조의 일종이다.

- 먼저 들어간 것이 먼저 나오는 선입선출(FIFO : First In First Out)형식의 자료구조이다.

  ※ 사용 예로 번호표 시스템을 들 수 있다.

  ※ 들어간 순서대로 나오므로 위 그림 기준으로 오른쪽에 데이터가 입력이 되고, 왼쪽 데이터부터 출력이 이루어진다.

 

큐를 작성할 코드에 활용할 구조체는 다음과 같다.

typedef struct Queue
{
    int data;
    struct Queue* NEXT;
}Queue;

 

 

Enqueue(입력)

void Enqueue(Queue** front, Queue** rear, int data)
{
    Queue* newNode = (Queue*)malloc(sizeof(Queue));
    newNode->data = data;
    newNode->NEXT = NULL;
    
    if(*front == NULL)
    {
        *front = newNode;
        *rear = newNode;
    }
    else
    {
        (*rear)->NEXT = newNode;
        *rear = newNode;
    }
}

  ※ Stack과는 다르게 연결리스트의 첫 노드와 마지막 노드를 참조할 변수를 인수로 받아 값을 넣어준다.

  ※ 결과적으로 Queue의 데이터가 1개일때는 front와 rear가 같은 노드를 참조하게되고, 2개 이상이 되면 rear는 마지막 노드를 참조하게 된다.

 

 

Dequeue(출력)

void Dequeue(Queue** front, Queue** rear)
{
    if(*front == NULL) return;
    
    printf("%d ", (*front)->data);
    
    Queue* deleteNode = *front;
    *front = (*front)->NEXT;
    if(*front == NULL)
        *rear = NULL;
    
    free(deleteNode);
}

  ※ 데이터를 출력하고 front가 참조하고 있는 노드를 할당 해제해준다.

  ※ front가 NULL이면 Queue에 더이상 데이터가 없는것이므로 rear의 참조도 NULL로 밀어준다.

 

위 과정을 그림으로 보면 다음과 같다.

  ※ 첫 노드는 front, 제일 마지막 노드는 rear가된다.

  ※ Enqueue : 새 데이터를 입력하면 Enqueue함수에서 노드를 동적할당하고 rear에 새로 할당한 노드를 참조해준다.

  ※ Dequeue : front가 참조하고 있는 데이터를 출력하고 front의 참조를 다음 노드로 변경해준다.

 

 

풀 소스코드는 다음과 같다.

#include <stdio.h>
#define MAX 10

typedef struct Queue
{
    int data;
    struct Queue* NEXT;
}Queue;

void Enqueue(Queue** front, Queue** rear, int data)
{
    Queue* newNode = (Queue*)malloc(sizeof(Queue));
    newNode->data = data;
    newNode->NEXT = NULL;
    
    if(*front == NULL)
    {
        *front = newNode;
        *rear = newNode;
    }
    else
    {
        (*rear)->NEXT = newNode;
        *rear = newNode;
    }
}

void Dequeue(Queue** front, Queue** rear)
{
    if(*front == NULL) return;
    
    printf("%d ", (*front)->data);
    
    Queue* deleteNode = *front;
    *front = (*front)->NEXT;
    if(*front == NULL)
        *rear = NULL;
    
    free(deleteNode);
}

void main()
{
    Queue* front = NULL, * rear = NULL;
    for(int i = 0; i < MAX; i++)
        Enqueue(&front, &rear, i);
        
    //현재 상태 : 0(front), 1, 2, 3, 4, 5, 6, 7, 8, 9(rear)
    
    for(int i = 0; i < MAX; i++)
        Dequeue(&front, &rear);
        
    //결과 : 0 1 2 3 4 5 6 7 8 9
}