[자료구조] 큐 (Queue)

큐 QUEUE

 

 

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 

형식을 말한다. 

영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.
프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. 

 

선형 큐 (linear queue)

 

은행업무에소 표를 뽑거나 줄을 서서 기다리는 사람들을 생각하면 쉬울 것 같습니다.

크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있습니다.

 

#define SIZE 5

class Queue
{
private:

    int front, rear;
    int queue[SIZE];

public:

    Queue()
        : front(0), rear(-1) {    }

    void EnQueue(int _data)
    {
        if (rear == SIZE - 1)
        {
            cout << "\nQueue OverFlow" << endl;
            return;
        }

        queue[++rear] = _data;
    }

    int DeQueue()
    {
        int returnValue = -1;

        if (front == rear + 1)
        {
            cout << "\nQueue Underflow" << endl;
            return -1;
        }

        returnValue = queue[front];
        queue[front] = -1;
        front++;

        return returnValue;
    }
};

int main()
{
    Queue queue = Queue();

    for (int i = 0; i < SIZE + 1; i++)
    {
        queue.EnQueue(i);
    }

    for (int i = 0; i < SIZE + 1; i++)
    {
        cout << queue.DeQueue() << " ";
    }

    cout << endl;

    return 0;
}

 

환영 큐 (Circular Queue)

 

선형 큐의 문제점을 보완한 것이 환형 큐입니다. 

front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식입니다.

 

 

#define SIZE 5

class Queue
{
private:

    int front;
    int rear;
    int queue[SIZE];

public:

    Queue()
        : front(0), rear(0) {}

    void Enqueue(int data)
    {
        if (front == (rear + 1) % SIZE)
        {
            cout << "\nQueue OverFlow" << endl;
            return;
        }
        else
        {
            queue[rear] = data;
            rear = (rear + 1) % SIZE;
        }
    }

    int Dequeue()
    {
        int returnData = -1;

        if (rear == front)
        {
            cout << "\nQueue Underflow" << endl;
            return -1;
        }
        else
        {
            returnData = queue[front];
            queue[front] = -1;
            front = (front + 1) % SIZE;
        }

        return returnData;
    }
};

int main()
{
    Queue queue = Queue();

    for (int i = 0; i < SIZE; i++)
    {
        queue.Enqueue(i);
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << queue.Dequeue() << " ";
    }

    cout << endl;

    return 0;
}