3.4 큐(Queue)

이번에는 큐를 알아보기로 해요.

큐는 자료를 한쪽으로 보관하고 다른쪽에서 꺼내는 FIFO(First In First Out) 방식의 자료구조입니다. 큐에 자료를 보관하는 연산을 PUT 혹은 ENQUEUE라 말하고 꺼내는 연산을 GET 혹은 DEQUEUE라고 말합니다. 그리고 보관할 위치 정보를 REAR, 꺼낼 위치 정보를 FRONT라고 말해요.

먼저 간단하게 보관하는 큐를 만들어 보기로 해요.

class Queue
{
    //여기에서는 자료를 저장할 버퍼를 생성할 때 정하기로 할게요. 
    //버퍼의 위치를 기억할 멤버를 선언하세요.
    int *buffer;
    //버퍼의 크기를 기억할 멤버도 필요하겠죠.
    const int size;
    //자료를 꺼낼 위치 정보도 기억해야 합니다.
    int front;
    //자료를 보관할 위치 정보도 기억해야 합니다.
    int rear;

생성자 메서드에서는 자료를 보관할 버퍼의 크기를 입력 인자로 받게 구현하세요.

public:
    Queue(int size):size(size)
    {
        //생성자에서는 자료를 보관할 버퍼를 동적으로 생성합니다.
        buffer = new int[size];
        //그리고 보관할 위치와 꺼낼 위치를 0으로 설정하세요.
        front = rear = 0;
    }

소멸자에서는 내부에서 동적으로 생성한 버퍼를 해제해야겠죠.

    ~Queue()
    {
        delete[] buffer;
    }

자료를 rear 위치에 보관하는 Put 메서드를 구현합시다.

큐는 스택과 달리 꺼내는 쪽과 보관하는 쪽이 다릅니다. 이러한 이유로 보관할 위치를 단순히 증가하는 형태로 작성하면 앞쪽에 보관한 것을 꺼내도 빈 공간을 사용할 수 없는 문제가 발생합니다. 이를 개선하는 방법은 몇 가지가 있는데 그 중에 가장 많이 사용하는 것이 원형 큐입니다.

원형 큐에서는 rear와 front를 0, 1, 2, …, size-1, 0, 1, 2, …. 형태로 이동합니다. 여기에서는 이를 수행하는 멤버 메서드 Next를 별도로 구현하기로 할게요.

큐 PUT 연산 GET 연산 
    bool Put(int data)
    {
        //버퍼가 꽉차면 보관할 수 없겠죠.
        if(IsFull())
        {
            return false;
        }
        //버퍼의 rear인덱스에 data를 보관하세요.
        buffer[rear] = data; 
        rear = Next(rear);
        return true;
    }

front 위치에 보관한 자료를 꺼내는 Put 메서드를 구현합시다. rear와 마찬가지로 0, 1, 2, …, size-1, 0, 1, 2, …. 형태로 이동합니다.

    int Get()
    {
        //비어있으면 0을 반환합시다. 
        //구현 목적에 따라 예외를 던질 수도 있겠죠.
        if(IsEmpty())
        {
            return 0;
        }
        //꺼낼 자료는 버퍼의 front 인덱스에 있는 자료입니다. 
        int re = buffer[front];
        //front를 다음 위치로 변경합니다.         
        front = Next(front);
        return re;
    }

비었는지 확인하는 IsEmpty 메서드를 제공합시다.

    bool IsEmpty()
    {
        //front와 rear가 같으면 비어있는 상태입니다.
        return front == rear;
    }
큐가 꽉 찬 상태

꽉 찼는지 확인한느 IsFull 메서드를 제공합시다. 원형 큐에서 버퍼에 모든 자료를 보관하면 front와 rear가 같아집니다. 보통 rear의 다음 위치가 front가 같으면 꽉 찬 것으로 처리합니다. 따라서 버퍼를 하나 사용하지 않는 것이죠. 이를 완충 지대라고 말해요.

    bool IsFull()
    {
        return Next(rear) == front;
    }

큐 내부에서 사용할 다음 인덱스를 계산하는 Next 메서드를 구현합시다. front나 rear는 0, 1, 2, …, size-1, 0, 1, 2, …. 형태로 이동해야 합니다. 이를 위해 1을 더한 값을 버퍼 크기로 나머지 연산하세요.

private:
    int Next(int now)
    {
        return (now+1)%size;
    }
};

간단히 테스트하는 코드를 작성합시다.

int main()
{
    Queue q(10);//크기가 10인 큐
    //큐에 자료를 보관하세요.
    q.Put(4); //4
    q.Put(7); //4 7
    q.Put(8); //4 7 8
    q.Put(2); //4 7 8 2
    //그리고 큐가 비어있지 않다면 꺼내서 출력하세요.
    while(q.IsEmpty() == false)
    {
        cout<<q.Get()<<" "; 
    }
    //실제 출력 결과는 보관한 순서와 일치하겠죠.
    cout<<endl;
    return 0;
}

▷ 실행 결과

4, 7, 8, 2

자료구조와 알고리즘 with C++