Queue | 큐

Queue

1. 먼저 들어간 데이터가 제일 먼저 나오는 FIFO(First In First Out)구조
2. 한쪽 끝에서 데이터를 넣고 반대쪽 끝에서 원소를 제거할 수 있는 자료구조

Queue 연산의 시간복잡도

• 데이터를 추가(push) -> O(1)
• 데이터를 제거(pop) - O(1)
• 맨 앞 데이터를 조회(front) -> O(1)
• 맨 뒤 데이터를 조회(rear) -> O(1)

Queue 응용 사례

1. 대기열(영화관, 공항 ...)
2. BFS
3. Flood Fill

Queue 구현

template<class T>
class Queue
{
private:
    int* queue;
    int size;
    int head, tail;
public:
    Queue<T>(int qSize) : size(qSize + 1), head(0), tail(0)
    {
        queue = new T[qSize + 1];
    }
    ~Queue<T>()
    {
        delete queue;
    }
    // 데이터 추가
    bool Enqueue(T data)
    {
        // 큐가 꽉찼다면
        if ((tail + 1) % size == head)
        {
            return false;
        }
        queue[tail] = data;
        tail = (tail + 1) % size;
        return true;
    }
    // 데이터 삭제
    int Dequeue()
    {
        int data;
        if (IsEmpty())
        {
            return -1;
        }
        data = queue[head];
        head = (head + 1) % size;
        return data;
    }
    // 비었는지 확인
    bool IsEmpty()
    {
        return head == tail;
    }
    // 꽉 찼는지 확인
    bool IsFull()
    {
        return (tail + 1) % size == head;
    }
};