3.4 큐(Queue) [소스 코드]

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

//큐
#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 뒤의 값을 꺼내게 구현하면 되겠죠. 여러분께서 한 번 작성해 보세요.

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

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