C/C++ 큐(Queue)

개요

큐(Queue)는 자료구조의 한 형태로 스택과 다르게 FIFO(First In First Out) 형태의 자료구조이다. FIFO는 말 그대로 선입선출이라는 의미로 먼저 들어간 데이터가 먼저 나온다나는 것이다. 쉽게 생각하여 표를 받기 위해 줄을 서는 것으로 보면 된다. 표를 받기 위해 먼저 줄을 서면 먼저 표를 받는 방식이다. 너비 우선 탐색, 캐시 구현 등의 다양한 곳에 사용된다. 큐의 구조와 큐를 구성하는 메소드 들에 대해 알아보자.

큐 구조체

struct Queue
{
    int size;
    int front;
    int rear;
    int* Q;
};

큐에는 줄의 시작(front)와 끝(rear)이 존재하며, 데이터가 통하는 구멍이 두 개라 볼 수 있다. size는 큐가 데이터를 담을 수 있는 개수를 나타내며, Q는 할당할 배열 포인터이다.

create함수-큐 생성 함수

void create(Queue *q, int size)
{
    q->size = size;
    q->front = q->rear = -1;
    q->Q = new int[q->size];
}

선언한 큐 구조체에 사이즈를 채우고, Q에 배열을 할당한다. front와 rear는 각각 배열의 인덱스를 나타내는데 아직 큐가 비어 있으므로 -1 인덱스를 할당한다.

enqueue함수-큐 데이터 입력함수

void enqueue(Queue *q, int x)
{
    if (q->rear == q->size -1)
        printf("Queue is Full");
    else
    {
        q->rear++;
        q->Q[q->rear] = x;
    }
}

먼저 rear이 큐의 끝에 도달했는지 체크한다. 데이터가 입력될 때마다, 큐의 rear이 증가하고 그 자리에 데이터가 들어간다. rear이 마지막 인덱스에 있으면 더 이상 데이터를 넣지 못한다. 아래의 그림을 보면 이해가 쉬울 것이다.

dequeue함수-데이터를 출력하는 함수

int dequeue(Queue *q)
{
    int x = -1;

    if (q->front == q->rear)
        printf("Queue is Empty\n");
    else
    {
        q->front++;
        x = q->Q[q->front];
    }
    return x;
}

front는 쉽게 말해 표를 주는 맨 앞 점원이라 보면 된다. front 뒤에 데이터가 존재하며, front를 통해 데이터가 나간다고 보면 된다. front와 rear 사이에 데이터가 저장되는데 front와 rear의 위치가 같다면 그 사이에 공간이 없다는 뜻이기에 큐가 비었음을 알 수 있다. 그게 아니라면, front의 위치가 한 칸 밀리고, 거기에 있는 데이터를 빼낸다.

큐의 데이터가 빠져나가는데 왜 배열의 데이터가 안 밀리냐고 궁금할 수 있다. 데이터가 나가는 위치를 고정해 놓고 데이터(표를 받는 사람)이 앞으로 움직이는 것은 소요가 크다. 대신에 데이터가 나가는 위치(front, 표를 주는 사람)이 뒤로 움직이면 똑같은 효과를 front만 옮겨서 얻을 수 있어 효율이 좋다.

Display함수-데이터 출력 함수

void Display(Queue q)
{
    for (int i = q.front+1; i <= q.rear; i++)
        printf("%d ", q.Q[i]);
    printf("\n");
}

배열의 값들을 front부터 rear까지 인덱스로 출력한다.

일자 큐의 단점

위에 구현한 일자 큐, 배열의 처음과 끝이 존재하는 큐는 효율이 좋지 않다. 데이터를 넣고 빼는 것을 반복해서 rear이 배열의 끝에 도달하면 front가 밀려 앞의 데이터가 큐에서 빠져나가서 공간이 비더라도 큐는 꽉 찼다고 판단하여 입력이 불가능하다. 이렇듯 일자 큐는 일회성이다. 이를 해결하기 위한 방법이 순환 큐이다. 배열의 끝이 배열의 처음으로 이어져서 rear는 배열의 마지막에서 한 칸 움직이면 배열의 처음으로 움직일 수 있다.

순환 큐 구현하기

순환 큐의 front rear 움직임은 그저 +1을 하지 않는다. 다음과 같은 식으로 움직인다.

rear = (rear + 1) % 배열의 size

이 방식으로 front와 rear는 배열의 끝에서 한 칸 움직이면 나머지 연산에 의해 배열의 처음 인덱스로 이동하게 된다. 똑같이 배열이 빈 것은 front와 rear이 같을 때이며, 큐가 꽉 찬 것은 rear에서 이동한 곳이 front일 때이다. 아래는 empty일 때와 full일 때의 상황이다.

순환 큐 enqueue함수

void enqueue(Queue *q, int x)
{
    if ((q->rear + 1) % q->size == q->front)
        printf("Queue is full");
    else
    {
        q->rear = ((q->rear + 1) % q->size);
        q->Q[q->rear] = x;
    }
}

rear 연산을 통해 다음 이동 자리가 front와 같다면 큐는 꽉 찬 것이며, 그게 아니라면 rear을 한 칸 뒤로 옮긴 뒤 데이터를 넣는다.

순환 큐 dequeue함수

 int dequeue(Queue *q)
{
    int x = -1;

    if (q->front == q->rear)
        printf("Queue is Empty\n");
    else
    {
        q->front = (q->front + 1) % q->size;
        x = q->Q[q->front];
    }
    return x;
}

rear과 front가 같다면 큐는 빈 것이며, 그게 아니라면 front를 뒤로 밀고, 거기의 데이터를 뽑는다.

마무리

큐에 대해 알아보았다. 스택과 다르게 FIFO 방식이며, 일반 큐와 일반 큐의 일회성을 보완한 순환 큐가 있다. 다음 글에서 연결 리스트로 큐를 구현해보고, C++ 클래스로 구현해보자