큐 (배열을 이용한 구현)

큐는 앞서 설명한 스택과 함께 언급되며 비교되는 자료구조이다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조(LIFO)이지만 큐는 먼저 들어간 데이터가 먼저 나온다. 이는 일상생활에서도 자주 접할 수 있다. 버스를 타기위해 줄을 서는데 먼저 선사람부터 먼저 타는 상황을 떠올려보자. 이렇듯 큐의 구조는 FIFO(First In First Out)의 구조로 이루어진다.

들어가기에 앞서
 1. Front와 Rear라는 용어가 나오는데 Front는 큐의 머리를 뜻하며 Rear는 큐의 꼬리를 뜻한다.
 2. 스택은 Push()와 Pop()으로 삽입, 삭제를 하지만 큐의 경우에는 Enqueue()와 Dequeue()로 삽입, 삭제가 이루어진다. 

큐의 구현에 대한 원리

① 데이터 삽입을 보자. 큐는 뒤에서 넣고 앞으로 빼는 구조로 이해하면 된다. Enqueue() 함수를 이용하여 최초로 A를 삽입할 경우 Front와 Rear의 위치는 같으며 추가되는 삽입마다 Rear가 그 다음 위치를 가리키며 이동한다.

Enqueue() 연산으로 A, B, C를 삽입하는 그림

② 데이터의 삭제를 보자. 큐는 먼저 들어간 것이 먼저 나와야하는 자료구조이다. 그렇기 때문에 A, B, C 순으로 삽입이 된 데이터를 A, B, C 순으로 삭제가 되어야한다. 아래의 그림을 보면 Dequeue() 함수 호출로 인해 A가 소멸이 되는데 삭제를 한 후 배열을 앞으로 한칸씩 이동시킴으로 인해 Front가 불필요한 상황이 발생된다. 또한 배열이 커짐에 따라 한 칸씩 이동시키는 것은 많은 연산량이 뒤따를 수 있다. 따라서 이 포스팅에서는 아래 그림과 같은 첫 번째 Dequeue 방식으로 구현하지 않는다.

첫 번째 Dequeue 방식

아래의 그림을보자. 두 번째 Dequeue 방식에서는 Dequeue를 할 때마다 Front의 위치만 오른쪽으로 이동하기 때문에 배열의 이동 연산이 필요하지가 않다. 하지만 아래의 상황을 보면 이 방법도 완벽하지가 않다.

두 번째 Dequeue 방식

아래의 그림을 보면 Enqueue 연산으로 D를 추가한 모습이다. 이는 배열이 꽉 차진 않았지만 더이상 Enqueue 연산을 통해 Rear를 오른쪽으로 이동할 수 없기 때문에 데이터를 추가할 수 없는 상황이다. 이 상황에서 어떻게 해야 추가가 가능할까? Rear를 앞부분으로 이동시키는 것을 이용하면 된다. 쉽게 말해서 Rear를 회전 시키는 것이다. Rear를 뒤쫓는 Front도 배열의 끝에 도달하면 앞 부분으로 이동을 시켜줘야하는데 이러한 방식으로 동작하는 큐를 원형 큐(Circular queue)라고 한다. 

배열이 비었음에도 불구하고 데이터를 추가할 수 없는 모습

원형 큐

원형큐의 기본 모양

앞서 우리는 Front와 Rear를 회전시켜서 구현을 한다면 더욱 효율적인 큐를 만들어진다는 것을 배웠다. 여기서 짚고 넘어가야할 문제가 하나 있다. 아래의 그림을 보자. Enqueue를 3번 호출하여 A,B,C를 삽입한 이후 Dequeue를 2번 호출한 그림이다.

왼쪽 : Enqueue를 3번 호출 / 오른쪽 : Dequeue를 2번 호출

위의 구조로 D를 추가하면서 큐를 추가해보고 C를 삭제해보면 Front가 Rear보다 한 칸 앞의 위치를 가리키고 있는 것을 알 수 있다. 이는 큐가 가득찼는지 비어있는지를 구분할 수가 없는 문제를 가지고 있다. 

왼쪽 : 가득찬 큐 / 오른쪽 : 빈 큐

개선된 큐

위의 문제를 해결하기 위해 우리는 배열을 꽉채우지 않는 방법으로 해결할 것이다. 이렇게 하면 저장 공간 하나를 낭비하게 되겠지만 이로 인해 문제점이 해결되므로 잃는 것 보다 얻는 것이 더 많기 때문에 이러한 부분을 참고하여 구현할 것이다.

개선된 큐의 형태

원형 큐가 가득찬 상태 : Rear보다 Front가 1만큼 앞에 있다.
원형 큐가 빈 상태 : Front와 Rear의 위치가 동일하다. 

이제 코드를 구현해보자.

#include <iostream>
 
using namespace std;
 
#define MAX_LENGTH 10
 
// 큐 구조체
typedef struct queue
{
    // 생성자
    queue() : front(0), rear(0) { memset(dataArr, 0, sizeof(dataArr)); }
 
    int front;
    int rear;
    int dataArr[MAX_LENGTH];
}QUEUE;
 
int NextPositionIndex(int position)
{
    // 배열의 마지막 요소의 인덱스일 경우
    if (position == MAX_LENGTH - 1)
        return 0;
 
    return position + 1;
}
 
void Enqueue(QUEUE* queue, int data)
{
    // 큐가 가득차있을 경우
    if (NextPositionIndex(queue->rear) == queue->front)
    {
        cout << "큐가 가득차있습니다." << endl;
        return;
    }
 
    // rear를 한칸 이동한 후 데이터 저장
    queue->rear = NextPositionIndex(queue->rear);
    queue->dataArr[queue->rear] = data;
}
 
bool IsEmpty(QUEUE* queue)
{
    // 비어있을 경우 true를 반환
    if (queue->front == queue->rear)
        return true;
 
    return false;
}
 
int Dequeue(QUEUE* queue)
{
    if (IsEmpty(queue))
    {
        cout << "큐가 비어있습니다." << endl;
        return 0;
    }
 
    // front 다음 위치를 반환
    queue->front = NextPositionIndex(queue->front);
    return queue->dataArr[queue->front];
}
 
int Peek(QUEUE* queue)
{
    if (IsEmpty(queue))
    {
        cout << "큐가 비어있습니다." << endl;
        return 0;
    }
 
    // front 다음 위치를 반환 (가장 앞의 데이터)
    return queue->dataArr[NextPositionIndex(queue->front)];
}
 
int main()
{
    // 큐 생성
    QUEUE newQueue;
 
    // 데이터 삽입
    for (int i = 0; i < 5; ++i)
    {
        Enqueue(&newQueue, i);
    }
 
    // 데이터 검색
    cout << Peek(&newQueue) << endl;
 
    // 데이터가 존재하지 않을 때까지 루프문 순회
    while (IsEmpty(&newQueue) == false)
    {
        // 데이터 출력
        cout << Dequeue(&newQueue) << endl;
    }
}