큐(Queue)

큐 란?

가장 먼저 들어간 데이터가 제일 먼저 나온다 (First In - First Out) FIFO
나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

큐의 주요 기능

DeQueue : 큐의 맨 앞에 있는 데이터를 제거 후 반환
EnQueue : 큐의 제일 뒤에 새로운 데이터 추가
Peek : 큐의 맨 앞에 있는 데이터를 반환

배열 형 큐 클래스

class MyQueue
{
public:
    MyQueue();

private:

    int Front;
    int Rear;
    int Capacity;
    int* Data;

public:

    void CreateQueue(const int& Size);
    bool IsEmpty();
    bool IsFull();
    int DeQueue();
    void EnQueue(const int& NewData);
    int Peek();
    void Show();
};

배열 형 큐 생성

외부로 부터 크기를 받고 크기만큼 동적할 당 후 Capacity를 통해 사이즈를 기억해준다.

void MyQueue::CreateQueue(const int& Size)
{
    Data = new int[Size];
    Capacity = Size;
}

배열 형 큐 체크 함수

비어있는지 확인하는 함수와 꽉차있는지 확인해주는 함수이다.

이때 Rear를 통해 Rear가 0보다 작으면 비어있고 0이상이면 1개의 이상의 데이터가 존재한다.

bool MyQueue::IsEmpty()
{
    return Rear < 0 ? true : false;
}

Rear와 Capacity - 1 와 같으면 꽉차있고 아니면 꽉차 있지않다.

bool MyQueue::IsFull()
{
    return Rear == Capacity - 1 ? true : false;
}

배열 형 큐 DeQueue

먼저 큐의 데이터가 있는지 확인 후

현재 Front의 값을 가져오고 Front를 증감시켜준다.

그런 다음 Dequeue를 하게 되면 증감된 Front로 인하여 다음 데이터를 가르키게 된다.

int MyQueue::DeQueue()
{
    if (IsEmpty())
    {
        return -1;
    }
    return Data[Front++];
}

배열 형 큐 EnQueue

먼저 큐가 꽉차있는지 확인 후 꽉차 있지 않으면

Rear를 먼저 증감연산자를 통해 증감시키고 배열에 접근하여 데이터를 넣어준다.

처음 Rear의 값은 -1로 시작해준다.

void MyQueue::EnQueue(const int& NewData)
{
    if (!IsFull())
    {
        Data[++Rear] = NewData;
    }
}

배열 형 큐 Peek

DeQueue는 데이터를 반환함과 동시에 반환한 다음 순서의 데이터가 1순위가 된다.

Peek는 단순히 제일 첫번째의 값을 반환해준다.

먼저 비어있는지 체크 후 비어있으면 -1의 값을 반환해주고 아니라면 데이터의 Front를 통해 접근하여 단순히 첫번째 데이터를

반환해준다.

int MyQueue::Peek()
{
    return IsEmpty() ? -1 : Data[Front];
}

배열 형 큐 메인 함수

int main()
{
    MyQueue* Queue = new MyQueue();

    Queue->CreateQueue(5);
    Queue->EnQueue(1);
    Queue->EnQueue(2);
    Queue->EnQueue(3);
    Queue->EnQueue(4);
    Queue->EnQueue(5);
    int a = Queue->Peek();
    std::cout << a << std::endl;
    Queue->DeQueue();
    Queue->Show();
}

Queue를 동적할당 해주고 CreateQueue를 통해 5개의 배열을 만들어 준다.

EnQueue를 통해 1,2,3,4,5를 넣어주며 Peek를 통해 데이터를 꺼내오고 출력하면 1이 출력되며

Dequeue를 통해 첫번째를 삭제하고 Show를 통해 출력을 하면 2,3,4,5가 출력됨을 볼 수 있다.

배열 형 큐 장단점

장점

데이터의 삽입 삭제가 쉽고 빠르다.
선형이기에 입력순서를 처리할때 유용하다.

단점

선형이기에 데이터를 추가를 하다보면 한계가 생기게 된다
삭제를 하게되면 삭제된 위치의 메모리는 남아있고 쓸모없게된다

- 배열 큐의 단점을 보완하기 위해 원형 큐가 존재한다.