3.4 큐(Queue) [디딤돌 자료구조와 알고리즘 with C++]

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 메서드를 구현합시다.

    bool Put(int data)

    {

버퍼가 꽉차면 보관할 수 없겠죠.

        if(IsFull())

        {

            return false;

        }

버퍼의 rear인덱스에 data를 보관하세요.

        buffer[rear] = data;

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

 

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

 

        rear = Next(rear);

        return true;

    }

 

 

front 위치에 보관한 자료를 꺼내는 Put 메서드를 구현합시다.

    int Get()

    {

비어있으면 0을 반환합시다. 구현 목적에 따라 예외를 던질 수도 있겠죠.

        if(IsEmpty())

        {

            return 0;

        }

꺼낼 자료는 버퍼의 front 인덱스에 있는 자료입니다.

        int re = buffer[front];

front를 다음 위치로 변경합니다. rear와 마찬가지로 0, 1, 2, ..., size-1, 0, 1, 2, .... 형태로 이동합니다.

        front = Next(front);

        return re;

    }

 

    bool IsEmpty()

    {

front와 rear가 같으면 비어있는 상태입니다.

        return front == rear;

    }

    bool IsFull()

    {

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

 

버퍼를 모두 사용하길 원한다면 보관한 자료 개수를 기억하는 멤버 필드를 추가하는 방법이 있습니다. 단순히 보관한 자료 개수가 0이면 빈 것이고 보관한 자료 개수가 버퍼의 크기와 같으면 꽉 찬 것으로 판별하는 것이죠. 여기에서는 완충 지대를 이용하는 형태로 구현할게요.

        return Next(rear) == front;

    }

 

private:

    int Next(int now)

    {

front나 rear는 0, 1, 2, ..., size-1, 0, 1, 2, .... 형태로 이동해야 합니다. 이를 위해 1을 더한 값을 버퍼 크기로 나머지 연산하세요.

        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

 

다음은 앞에서 작성한 원형 큐 코드입니다.

//큐

#include <iostream>

using namespace std;

 

class Queue

{

    int *buffer;

    const int size;

    int front;

    int rear;

 

public:

    Queue(int size):size(size)

    {       

        buffer = new int[size];

        front = rear = 0;

    }

    ~Queue()

    {

        delete[] buffer;

    }

 

    bool Put(int data)

    {

        if(IsFull())

        {

            return false;

        }

        buffer[rear] = data;

        rear = Next(rear);

        return true;

    }

    int Get()

    {

        if(IsEmpty())

        {

            return 0;

        }

        int re = buffer[front];

        front = Next(front);

        return re;

    }

    bool IsFull()

    {

        return Next(rear) == front;

    }

    bool IsEmpty()

    {

        return front == rear;

    }

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

 

큐도 연결리스트를 이용하여 구현할 수도 있어요. PUT 연산에서 tail 앞에 보관하고 POP 연산에서 head 뒤의 값을 꺼내게 구현하면 되겠죠. 여러분께서 한 번 작성해 보세요.

 

그런데 큐를 구현하는 것은 개발자에게 큰 의미는 없어요. 개발자에게 필요하는 것은 언제 큐를 사용하는지 판단하고 무엇을 언제 보관하고 언제 꺼내서 어떻게 사용할 것인지를 결정하는 능력이 필요합니다.

 

이 책에서는 스케쥴러 시뮬레이션과 깊이 우선 탐색 알고리즘에서 큐를 사용하는 실습해 볼 거예요.

 

STL에서는 큐를 템플릿 클래스 queue로 제공하고 있습니다.

//STL에서 제공하는 큐 사용

#include <iostream>

STL에서 제공하는 큐를 사용하려면 queue 파일을 포함하세요.

#include <queue>

using namespace std;

 

int main()

{

    queue<int> q;//int 형식을 보관하는 큐

STL의 큐에 자료를 보관하는 메서드는 push입니다. 전산학에서 PUT 연산과 이름이 다른 점에 주의하세요.

    q.push(4); //4

    q.push(7); //4 7

    q.push(8); //4 7 8

    q.push(2); //4 7 8 2

 

    while(q.empty() == false)

    {

큐에서 가장 먼저 보관한 자료를 확인하는 메서드는 front입니다.

        cout<<q.front()<<" ";  //가장 먼저 보관한 자료 확인

그리고 가장 먼저 보관한 자료를 꺼내는 메서드는 pop이예요. 전산학에서 GET 연산과 이름이 달라요.

        q.pop();//가장 먼저 보관한 자료 꺼내기

    }

    cout<<endl;

    return 0;

}

 

 

▷실행 결과

4,7,8,2