[C++/STL] Queue 정리

C++ 표준 템플릿 라이브러(STL)에서 제공하는 std::queue는 FIFO(First In, First Out - 선입선출) 구조를 구현한 컨테이너 어댑터(Container Adapter)이다.

 

Queue의 핵심 개념

• FIFO (First In, First Out): 가장 먼저 들어간 데이터가 가장 먼저 나온다. (예: 줄 서기, 프린터 인쇄 대기열)
• 제한된 접근: 데이터는 맨 뒤(Back)로만 추가되고, 맨 앞(Front)에서만 제거 및 조회할 수 있다. 스택과 마찬가지로 임의 접근(인덱스 조회) 및 반복자(Iterator)를 통한 중간 순회가 불가능하다.

 

주요 멤버 함수 및 시간 복잡도

std::queue의 모든 주요 연산은 $O(1)$의 시간 복잡도를 가진다.

push(val)	큐의 맨 뒤(Back)에 원소 val을 추가한다.	$O(1)$
emplace(args...)	큐의 맨 뒤에 원소를 직접 생성하여 추가한다.	$O(1)$
pop()	큐의 맨 앞(Front) 원소를 제거한다. (값을 반환하지 않음)	$O(1)$
front()	큐의 맨 앞(Front) 원소에 대한 참조를 반환한다.	$O(1)$
back()	큐의 맨 뒤(Back) 원소에 대한 참조를 반환한다.	$O(1)$
empty()	큐가 비어있는지 여부를 반환한다. (true/false)	$O(1)$
size()	큐에 저장된 원소의 개수를 반환한다.	$O(1)$
swap(other_queue)	두 큐의 내용을 서로 바꾼다.	$O(1)$

 

주의사항: 큐가 비어있는 상태(empty() == true)에서 front(), back(), pop()을 호출하면 정의되지 않은 동작(Undefined Behavior)이 발생하므로 항상 사전에 비어있는지 체크해야 한다.

 

컨테이너 어댑터로서의 Queue와 내부 컨테이너의 비밀

std::queue 역시 스스로 메모리를 관리하지 않고 기존 컨테이너를 래핑하여 동작한다.

• 기본 내부 컨테이너: std::deque를 기본으로 사용한다.
• 사용 가능한 내부 컨테이너: std::list 등으로 변경할 수 있다.

#include <queue>
#include <list>

std::queue<int> q1;                         // 기본 deque 기반 큐
std::queue<int, std::list<int>> q2;         // list 기반 큐

 

왜 std::vector는 std::queue의 내부 컨테이너로 사용할 수 없을까?

std::stack은 std::vector를 내부 컨테이너로 쓸 수 있었던 반면, std::queue는 std::vector를 내부 컨테이너로 사용할 수 없다.

• 이유: std::queue는 맨 앞의 원소를 제거하는 pop() 연산을 위해 내부 컨테이너의 pop_front() 멤버 함수를 사용한다.
• 하지만 std::vector는 구조 특성상 맨 앞의 원소를 지우면 뒤의 원소들을 앞으로 한 칸씩 모두 당겨야 하므로 $O(N)$의 막대한 비용이 든다. 이 때문에 std::vector에는 pop_front() 함수 자체가 아예 설계되어 있지 않으며, 결과적으로 std::queue의 내부 컨테이너로 지정할 경우 컴파일 에러가 발생한다.

 

Queue의 다양한 종류 (Varieties of Queues)

실제 개발 및 알고리즘 풀이에서는 상황에 맞는 다양한 변형 큐가 사용된다.

 

① 선형 큐 (Linear Queue)

• 우리가 흔히 아는 기본 std::queue
• 단점: 일렬로 늘어선 배열 형태의 선형 큐는 pop을 할 때마다 앞쪽에 빈 메모리 공간이 생기지만, 이를 재사용하려면 데이터를 앞으로 이동시켜야 하는 낭비가 생긴다. (이를 보완하기 위해 링 버퍼 형태의 원형 큐가 고안되었음.)

② 원형 큐 (Circular Queue / Ring Buffer)

• 배열의 마지막 인덱스가 다시 첫 번째 인덱스로 연결되는 원형 구조의 큐이다.
• 장점: 고정된 크기의 배열에서 포인터(Front, Rear)의 회전 연산((index + 1) % MaxSize)을 통해 메모리 낭비 없이 빈 공간을 무한히 재사용할 수 있다.
• 용도: 네트워크 버퍼, 오디오 스트리밍 데이터 캐싱 등 고정 크기 제한이 있는 시스템 소프트웨어에 필수적

③ 덱 (Deque - Double-Ended Queue)

• 양쪽 끝(Front, Back) 모두에서 삽입과 삭제가 자유롭게 가능한 선형 자료구조이다.
• C++ 지원: std::deque로 제공된다.
• 특징: 큐와 스택의 역할을 동시에 수행할 수 있어 매우 유연하며, 인덱스를 통한 임의 접근([] 연산자)도 $O(1)$에 지원한다.

④ 우선순위 큐 (Priority Queue)

• FIFO 순서가 아니라, 데이터마다 부여된 우선순위(Priority)에 따라 우선순위가 높은 데이터가 먼저 나가는 큐이다.
• C++ 지원: std::priority_queue로 제공되며, 내부적으로 힙(Heap) 자료구조로 구현되어 있다.
• 시간 복잡도: 삽입 및 삭제 연산에 $O(\log N)$, 최댓값/최솟값 조회에 $O(1)$이 소요된다.
• 용도: 다익스트라(Dijkstra) 최단 경로 알고리즘, CPU 스케줄링(우선순위 기반), 허프만 코딩 등.

 

예제 코드

#include <iostream>
#include <queue>
#include <string>

int main() {
    // 일반 큐 선언 및 활용
    std::queue<std::string> printQueue;

    printQueue.push("문서_A.pdf");
    printQueue.push("사진_B.png");
    printQueue.emplace("보고서_C.docx"); // 직접 생성하여 추가

    std::cout << "--- 일반 큐 출력 (FIFO) ---" << std::endl;
    while (!printQueue.empty()) {
        std::cout << "인쇄 시작: " << printQueue.front() << std::endl;
        printQueue.pop(); // 출력 완료 후 제거
    }

    // 우선순위 큐 선언 및 활용 (기본은 내림차순 - 최대 힙)
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "\n--- 우선순위 큐 출력 (기본: 내림차순) ---" << std::endl;
    while (!pq.empty()) {
        std::cout << "값: " << pq.top() << std::endl; // top()을 통해 최댓값 접근
        pq.pop();
    }

    return 0;
}