[자료구조] Queue (feat. C 언어)

정의

 

큐(Queue)는 자료 구조 중 선형 구조에 해당되며 먼저 삽입된 자료 순서대로 삭제되는 선입선출(FIFO : First In Fisrt Out) 방식으로 이루어져 있다. 자료를 삽입할 때는 enqueue라고 하며 반대로 삭제할 때는 dequeue라고 한다. 가장 먼저 삽입된 위치를 front, 가장 나중에 삽입된 위치를 rear라고 한다.

 

 

선입선출(FIFO : First In Fisrt Out) 방식

 

 

특징

 

• 선형 구조
• 선입선출(FIFO : First In Fisrt Out)
• 삽입 - enqueue, 삭제 - dequeue
• 가장 먼저 삽입 위치 - front, 가장 나중 삽입 위치 - rear 
• 운영체제의 작업 스케줄링

 

연산

 

큐의 구조

 

• enqueue 연산 : 큐가 비어있는 경우 추가되는 데이터가 front 및 rear가 된다. 큐에 데이터가 추가될 때 현 rear가 가리키는 포인터는 추가되는 노드의 주소가 되며 추가되는 노드가 가리키는 포인터는 null값을 가진다. 이후 추가 되는 노드가 rear가 된다.

 

enqueue 연산

 

• dequeue 연산 : 데이터 삭제 시 front가 가리키는 노드가 front가 되며 삭제 되는 노드는 free 함수를 통해 메모리를 해제한다.

 

dequeue 연산

 

 

구현

 

• init_queue 함수 : 큐 초기화

 

void init_queue(struct Queue* queue) // queue 이니셜라이징
{
    queue->front = NULL;
    queue->rear = NULL;
    queue->count = 0;
}

 

• enqueue 함수 : 큐에 데이터 삽입

 

void enqueue(struct Queue* queue, int data) // data를 queue 넣어주는 함수
{
    struct Node_queue* node = (struct Node_queue*)malloc(sizeof(struct Node_queue));
    node->data = data;
 
    if (queue->count == 0) // queue가 비어있는 경우
    {
        queue->front = node;
    }
 
    else
    {
        queue->rear->next = node; // dequeu 시 사라지는 node는 front이기 때문에 front 쪽에서 부터 연쇄되야함
    }
 
    queue->rear = node;
    queue->count += 1;
}

 

• dequeue 함수 : 큐에서 데이터 삭제 후 데이터 값 반환

 

int dequeue(struct Queue* queue) // data를 queue에서 제거해주는 함수, data는 FIFO 형식(First In First Out) : 맨 처음에 들어온 data가 맨 첫번째로 제거 된다.
{
    int data;
    struct Node_queue* node = queue->front;
 
    if (queue->count == 0) // queue가 비어있는 경우
    {
        printf("남은 data가 없습니다.\n");
        return 0;
    }
 
    data = node->data;
    queue->front = node->next;
    queue->count -= 1;
    free(node);
    return data;
}

 

• 전체 구조

 

struct Node_queue {
 
    int data;
    struct Node_queue* next;
};
 
 
struct Queue {
 
    struct Node_queue* front;
    struct Node_queue* rear;
    int count;
};
 
 
void init_queue(struct Queue* queue);
void enqueue(struct Queue* queue, int data);
int dequeue(struct Queue* queue);
 
 
void init_queue(struct Queue* queue) // queue 이니셜라이징
{
    queue->front = NULL;
    queue->rear = NULL;
    queue->count = 0;
}
 
 
void enqueue(struct Queue* queue, int data) // data를 queue 넣어주는 함수
{
    struct Node_queue* node = (struct Node_queue*)malloc(sizeof(struct Node_queue));
    node->data = data;
 
    if (queue->count == 0) // queue가 비어있는 경우
    {
        queue->front = node;
    }
 
    else
    {
        queue->rear->next = node; // dequeue 시 사라지는 node는 front이기 때문에 front 쪽에서 부터 연쇄되야함
    }
 
    queue->rear = node;
    queue->count += 1;
}
 
 
int dequeue(struct Queue* queue) // data를 queue에서 제거해주는 함수, data는 FIFO 형식(First In First Out) : 맨 처음에 들어온 data가 맨 첫번째로 제거 된다.
{
    int data;
    struct Node_queue* node = queue->front;
 
    if (queue->count == 0) // queue가 비어있는 경우
    {
        printf("남은 data가 없습니다.\n");
        return 0;
    }
 
    data = node->data;
    queue->front = node->next;
    queue->count -= 1;
    free(node);
    return data;
}