[C++ Data Structure] 큐

큐

큐(Queue)는 FIFO(First In First Out)의 구조를 가진 자료구조입니다.
가장 처음에 삽입된 요소가 가장 먼저 제거됩니다.

대표적으로 서버 접속 대기열의 구조가 큐입니다.
이 외에도 프린터를 쓸 때 인쇄 대기열도 구조가 큐입니다.

데이터의 순서를 유지하면서 처리해야 하는 상황에서 유용하게 사용됩니다.
그래프나 트리에서 폭 너비 우선 탐색(BFS)알고리즘 구현에 사용됩니다.
키보드, 마우스 등 이벤트를 순서대로 처리할 때 사용됩니다.
큐를 활용해 캐싱 시스템에서 오래된 데이터를 교체할 때 사용됩니다.

큐는 컨테이너 어댑터(Container Adapter)로 다른 컨테이너를 기반으로 동작합니다. 기본적으로 std::deque를 사용하지만, std::list같은 다른 컨테이너를 기반으로 사용할 수 있습니다.

삽입, 제거, 요소 접근, 비어 있는지 확인하는 모든 시간 복잡도는 $O(1)$입니다.

배열 기반 큐는 고정된 크기를 가지며, 초과할 경우 오버플로우가 발생합니다.
이때 요소 제거 시 앞쪽 요소를 이동해야 할 수 있어 비효율적일 수 있습니다.

큐 구현

class Queue {
private:
    std::vector<int> queue;

public:
    Queue() = default;

    // 큐의 첫 번째 원소 반환
    int front() const {
        if (queue.empty()) {
            throw std::out_of_range("큐가 비어있어요!");
        }
        return queue.front();
    }

    // 큐의 마지막 원소 반환
    int back() const {
        if (queue.empty()) {
            throw std::out_of_range("큐가 비어있어요!");
        }
        return queue.back();
    }

    // 큐에 원소 추가
    void push(int value) {
        queue.push_back(value);
    }

    // 큐의 첫 번째 원소 제거
    void pop() {
        if (queue.empty()) {
            throw std::underflow_error("큐가 비어서 꺼낼게 없어요!");
        }
	        queue.erase(queue.begin());
    }
};