[자료구조] 큐(Queue)란?

큐란?

큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First in First out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

스택은 아래 부분이 막히고 윗 부분이 뚫린 통과 같았다면, 큐는 양 쪽이 뚫린 통과 같다. 스택이 가장 윗부분에서 데이터를 넣고 꺼냈다면, 큐는 front에서 dequeue 연산이 진행되고, rear 부분에서 enqueue 연산이 진행된다.

 

C언어 구현

큐는 배열 혹은 연결리스트로 구현할 수 있다. 배열로 구현할 시에는 여러가지 문제점이 발생할 수 있다. 여기서는 연결리스트를 이용해 큐를 구현해보도록 한다.

1. 노드 정의 및 큐 초기화

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node 
{
    int data;
    struct Node *next;
}Node;
 
 
typedef struct Queue 
{
    Node *front;
    Node *rear; 
    int count; // 큐 안의 노드 개수  
}Queue;
 
void initQueue(Queue *queue)
{
    queue->front = queue->rear = NULL; 
    queue->count = 0;    // 큐 안의 노드 개수를 0으로 설정
}


출처: https://code-lab1.tistory.com/6?category=1213002 [코드 연구소:티스토리]

가장 먼저 노드를 정의하고, Queue 구조체를 정의한다. 큐를 초기화하는 initQueue() 함수를 이용해 front와 rear를 Null 로 초기화하고, 큐 안의 노드 개수를 나타내는 count를 0으로 초기화한다.

 

2. isEmpty() 함수

큐에서 데이터를 뽑아낼 때 큐가 비어있다면 오류가 발생할 수 있다.

따라서 큐가 비어 있는지 확인하는 함수인 isEmpty()가 필요하다.

int isEmpty(Queue *queue){
    return queue->count == 0;    // 큐안의 노드 개수가 0이면 빈 상태
}


출처: https://code-lab1.tistory.com/6?category=1213002 [코드 연구소:티스토리]

큐가 비어있는지 확인하는 함수는 두 가지 방법을 사용할 수 있다.

queue->front == NULL && queue->rear==NULL

첫번째 경우는 큐의 front와 rear가 null일 경우이다. 이런 경우는 비어있을 때뿐이기 때문이다.

두번째 경우는 큐안의 노드 개수가 0이라면 큐가 빈 상태로 취급한다.

3. 큐의 삽입(enqueue)

큐의 데이터 삽입은 rear 부분, 즉 큐의 맨 뒤에서 발생한다. 가장 먼저 새로운 노드를 만들어 data를 할당하고, 이후 큐에 집어 넣는다.

void enqueue(Queue *queue, int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node)); // newNode 생성
    newNode->data = data;
    newNode->next = NULL;
 
    if (isEmpty(queue))    // 큐가 비어있을 때
    {
        queue->front = newNode;       
    }
    else    // 비어있지 않을 때
    {
        queue->rear->next = newNode;    //맨 뒤의 다음을 newNode로 설정
    }
    queue->rear = newNode;    //맨 뒤를 newNode로 설정   
    queue->count++;    //큐안의 노드 개수를 1 증가
}


출처: https://code-lab1.tistory.com/6?category=1213002 [코드 연구소:티스토리]

코드를 보고 이해가 가지 않는다면 다음 그림을 보자.

 큐가 비어있을 때 enqueue

큐가 비어있을 때 데이터를 삽입하면, front와 rear가 동일하게 newNode를 가리키게 된다. 

큐가 비어있지 않을 때 enqueue

큐가 비어있지 않을 때 데이터를 삽입하면 front는 가장 앞의 노드를 가리키고 rear는 가장 뒤의 노드 즉, 방금 삽입한 노드를 가리키게 된다. 이는 다음과 같은 과정을 거쳐서 이루어진다.

 

1. newNode 생성

2. rear의 next 가 newNode를 가리키도록 설정

3. rear가 newNode를 가리키도록 설정

 

next 포인터가 enqueue 되는 방향과 반대로 설정되는게 어색할 수도 있으나, 이는 dequeue 연산을 위해서다. dequeue 연산에서 자세히 보도록 하자.

 

4. 큐의 데이터 반환(dequeue)

int dequeue(Queue *queue)
{
    int data;
    Node *ptr;
    if (isEmpty(queue))    //큐가 비었을 때
    {
        printf("Error : Queue is empty!\n");
        return 0;
    }
    ptr = queue->front;    //맨 앞의 노드 ptr 설정 
    data = ptr->data;    // return 할 데이터  
    queue->front = ptr->next;    //맨 앞은 ptr의 다음 노드로 설정
    free(ptr);    // ptr 해제 
    queue->count--;    //큐의 노드 개수를 1 감소
    
    return data;
}


출처: https://code-lab1.tistory.com/6?category=1213002 [코드 연구소:티스토리]

큐에서 데이터 반환은 큐의 맨 앞 front 에서 발생한다. 

 

큐가 비어 있을 경우에는 데이터 반환을 할 수 없으므로 오류 메시지를 출력한다. 큐가 비어 있지 않다면 맨 앞의 노드의 데이터를 반환하고, 해당 노드를 free 시켜준다. 이후 큐의 노드 개수를 1 감소 시킨다.

 

큐가 비어있지 않을 경우 데이터를 반환하는 과정을 그림으로 자세히 알아보자.

 

 

ptr 이 front를 가리키도록 설정

 

가장 먼저 ptr이 큐의 front를 가리키도록 한다. 이 때 반환할 데이터를 따로 저장한다. (여기서는 로컬 변수 int data)

 

 

front 가 ptr->next를 가리키도록 설정

 

이후 front 가 ptr->next를 가리키도록 한다. 이를 위해서 enqueue 과정에서 next 포인터를 역방향으로 설정한 것이다.

 

 

ptr 해제

 

이후 ptr을 free(메모리 해제)시켜주고, 큐의 노드 개수를 1감소시킨다. 마지막으로 따로 저장한 data를 반환하면 dequeue 과정이 완료된다.

 

전체 코드

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node 
{
    int data;
    struct Node *next;
}Node;
 
 
typedef struct Queue 
{
    Node *front;
    Node *rear; 
    int count; // 큐 안의 노드 개수  
}Queue;
 
void initQueue(Queue *queue)
{
    queue->front = queue->rear = NULL; 
    queue->count = 0;    // 큐 안의 노드 개수를 0으로 설정
}
 
int isEmpty(Queue *queue)
{
    return queue->count == 0;    // 큐안의 노드 개수가 0이면 빈 상태
}
 
void enqueue(Queue *queue, int data)
{
    Node *newNode = (Node *)malloc(sizeof(Node)); // newNode 생성
    newNode->data = data;
    newNode->next = NULL;
 
    if (isEmpty(queue))    // 큐가 비어있을 때
    {
        queue->front = newNode;       
    }
    else    // 비어있지 않을 때
    {
        queue->rear->next = newNode;    //맨 뒤의 다음을 newNode로 설정
    }
    queue->rear = newNode;    //맨 뒤를 newNode로 설정   
    queue->count++;    //큐안의 노드 개수를 1 증가
}
 
int dequeue(Queue *queue)
{
    int data;
    Node *ptr;
    if (isEmpty(queue))    //큐가 비었을 때
    {
        printf("Error : Queue is empty!\n");
        return 0;
    }
    ptr = queue->front;    //맨 앞의 노드 ptr 설정 
    data = ptr->data;    // return 할 데이터  
    queue->front = ptr->next;    //맨 앞은 ptr의 다음 노드로 설정
    free(ptr);    // ptr 해제 
    queue->count--;    //큐의 노드 개수를 1 감소
    
    return data;
}
 
int main(void)
{
    int i;
    Queue queue;
 
    initQueue(&queue);//큐 초기화
    for (i = 1; i <= 10; i++) 
    {
        enqueue(&queue, i);
    }
    while (!isEmpty(&queue))    // 큐가 빌 때까지 
    {
        printf("%d ", dequeue(&queue));    //큐에서 꺼내온 값 출력
    }
    printf("\n");
    return 0;
}
출처: https://code-lab1.tistory.com/6?category=1213002 [코드 연구소:티스토리]