[C++ STL] queue 완벽 정리: 기본부터 심화까지 (면접 대비)

Date: 2025.05.25 Updated: 2025.05.25

카테고리: STL

태그: algorithm C++ coding test data structure queue implementation STL queue

1. 📚 queue의 개념

C++ STL(Standard Template Library)에서 std::queue는 FIFO(First In First Out) 원칙을 따르는 컨테이너 어댑터로, 기본적으로 std::deque를 기반으로 구현되며, 그 단순성과 효율성 덕분에 다양한 상황에서 활용된다.

📌 queue의 특징

FIFO 구조: 먼저 삽입된 요소가 가장 먼저 제거되는 선입선출 구조를 따른다.
제한된 접근: 큐의 맨 앞(front)과 맨 뒤(back)에서만 요소를 추가하거나 제거할 수 있다.
컨테이너 어댑터: 실제 컨테이너를 감싸서 큐 인터페이스를 제공하는 래퍼 클래스이다.
- 어댑터 패턴: 기존 컨테이너의 인터페이스를 새로운 인터페이스로 변환하는 디자인 패턴을 사용한다.
- 기반 컨테이너: std::deque, std::list 등이 기반 컨테이너로 사용될 수 있다.
- 인터페이스 제한: 기반 컨테이너의 모든 기능을 노출하지 않고, 큐에 필요한 기능만 제공한다.
- 템플릿 매개변수:
```
template <class T, class Container = deque<T>>
class queue;
```
  - T: 저장할 요소의 타입
  - Container: 기반이 될 컨테이너 타입 (기본값: std::deque<T>)
- 요구사항: 기반 컨테이너는 다음 멤버 함수들을 반드시 제공해야 한다.
  - front(): 첫 번째 요소 접근
  - back(): 마지막 요소 접근
  - push_back(): 끝에 요소 추가
  - pop_front(): 첫 번째 요소 제거
  - empty(): 컨테이너가 비어있는지 확인
  - size(): 컨테이너의 크기 반환
기본 컨테이너: 기본적으로 std::deque를 사용하지만, 다른 컨테이너로 변경 가능하다.

🔍 컨테이너 어댑터의 장점

코드 재사용: 기존 컨테이너의 구현을 재사용하여 코드 중복을 방지한다.
유연성: 기반 컨테이너를 쉽게 교체할 수 있어 상황에 맞는 최적화가 가능하다.
인터페이스 단순화: 복잡한 컨테이너의 인터페이스를 단순하고 직관적인 인터페이스로 변환한다.
일관성: STL의 다른 컨테이너 어댑터(std::stack, std::priority_queue)와 일관된 사용법을 제공한다.

💡 컨테이너 어댑터 사용 예시

// 기본 컨테이너(std::deque)를 사용하는 큐
std::queue<int> default_queue;

// std::list를 기반으로 하는 큐
std::queue<int, std::list<int>> list_queue;

// 기존 컨테이너로 초기화
std::deque<int> deq = {1, 2, 3, 4, 5};
std::queue<int> initialized_queue(std::move(deq));

2. 💻 queue의 기본 사용법

📋 queue 선언 및 초기화

기본 선언:

std::queue<T> queue_name;  // T는 요소의 타입

다른 컨테이너를 사용한 선언:

std::queue<T, std::list<T>> queue_name;  // list를 기반으로 하는 큐

기존 컨테이너로 초기화:

std::deque<int> deq = {1, 2, 3, 4, 5};
std::queue<int> q(std::move(deq));  // deque를 이동하여 초기화

🔧 요소 추가 및 삭제

요소 추가:

q.push(6);        // 맨 뒤에 요소 추가
q.emplace(7);     // 맨 뒤에 요소를 직접 생성하여 추가 (임시 객체 생성 방지)

요소 제거:

q.pop();          // 맨 앞 요소 제거 (반환값 없음)

🔍 요소 접근

맨 앞 요소 접근:

int front_element = q.front();  // 맨 앞 요소 반환 (제거하지 않음)

맨 뒤 요소 접근:

int back_element = q.back();    // 맨 뒤 요소 반환 (제거하지 않음)

큐 상태 확인:

size_t size = q.size();     // 큐의 현재 크기 반환
bool is_empty = q.empty();  // 큐가 비어있는지 확인

3. ⚡ queue의 내부 작동 및 성능

📊 기본 컨테이너 선택

std::deque (기본값):
- 양쪽 끝에서 O(1) 시간에 삽입/삭제가 가능하다.
- 메모리 블록이 분산되어 있어 큰 데이터에 적합하다.
- 중간 접근이 필요한 경우 비효율적이다.
std::list:
- 양쪽 끝에서 O(1) 시간에 삽입/삭제가 가능하다.
- 메모리 오버헤드가 크다.
- 중간 삽입/삭제가 필요한 경우에 유용하다.

🚀 성능 고려사항

기본 컨테이너 선택 기준:
- 대부분의 경우 기본 std::deque가 최적의 선택이다.
- 메모리 효율성이 중요하면 std::list를 고려한다.
- 중간 삽입/삭제가 필요한 경우 std::list를 고려한다.

4. 🛠️ queue의 주요 멤버 함수

함수	설명	시간 복잡도
`empty()`	큐가 비어있는지 확인	O(1)
`size()`	큐의 현재 크기 반환	O(1)
`front()`	맨 앞 요소 반환	O(1)
`back()`	맨 뒤 요소 반환	O(1)
`push(val)`	맨 뒤에 요소 추가	O(1)
`emplace(args)`	맨 뒤에 요소를 직접 생성하여 추가	O(1)
`pop()`	맨 앞 요소 제거	O(1)
`swap(other)`	다른 큐와 내용을 맞바꿈	O(1)

5. 🔄 큐 구현 예시

📝 기본적인 queue 사용 예시

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

int main() {
    // 큐 선언 및 초기화
    std::queue<std::string> q;

    // 요소 추가
    q.push("First");   // 맨 뒤에 "First" 추가
    q.push("Second");  // 맨 뒤에 "Second" 추가
    q.push("Third");   // 맨 뒤에 "Third" 추가

    // 큐 순회 (비어있을 때까지)
    std::cout << "큐 내용 (FIFO 순서):\n";
    while (!q.empty()) {
        std::cout << q.front() << "\n";  // 맨 앞 요소 출력
        q.pop();                         // 맨 앞 요소 제거
    }

    return 0;
}

🔄 다른 컨테이너를 사용한 큐 예시

#include <iostream>
#include <queue>
#include <list>

int main() {
    // list 기반 큐
    std::queue<int, std::list<int>> list_queue;
    list_queue.push(1);  // 맨 뒤에 1 추가
    list_queue.push(2);  // 맨 뒤에 2 추가
    list_queue.push(3);  // 맨 뒤에 3 추가

    // 큐의 내용 출력
    std::cout << "List 기반 큐:\n";
    while (!list_queue.empty()) {
        std::cout << list_queue.front() << " ";  // 맨 앞 요소 출력
        list_queue.pop();                        // 맨 앞 요소 제거
    }
    std::cout << "\n";

    return 0;
}

6. ⚠️ 주의사항 및 팁

🚨 빈 큐 접근

front(), back()이나 pop()을 빈 큐에 호출하면 정의되지 않은 동작이 발생한다.
항상 empty()로 확인 후 접근해야 한다.

🔄 반복자 사용 불가

큐는 반복자를 제공하지 않는다.
모든 요소에 접근하려면 pop()을 사용하여 순차적으로 제거해야 한다.

🧹 메모리 관리

큐는 기본 컨테이너의 메모리 관리 방식을 따른다.
std::deque를 사용할 경우 메모리 블록 관리를 주의해야 한다.
- 메모리 블록 관리란?
  - std::deque는 여러 개의 고정 크기 메모리 블록으로 데이터를 저장
  - 각 블록은 연속된 메모리 공간이지만, 블록들 사이는 연속적이지 않음
  - 새로운 블록은 필요할 때마다 동적으로 할당됨
- 주의해야 하는 이유:
  - 블록 단위로 메모리를 할당/해제하므로 메모리 단편화 발생 가능
  - 블록 크기가 작으면 메모리 할당/해제가 자주 발생하여 성능 저하
  - 블록 크기가 크면 사용하지 않는 메모리 공간이 많아짐
  - 대용량 데이터 처리 시 메모리 사용량 예측이 어려움
- 최적화 전략:
  - 예상되는 데이터 크기에 맞는 적절한 블록 크기 선택
  - 메모리 사용량 모니터링
  - 필요한 경우 기반 컨테이너(std::deque)에 직접 접근하여 shrink_to_fit() 호출
    std::queue<int> q; // ... 큐 사용 ... // 기반 컨테이너에 접근하여 메모리 최적화 std::deque<int>& underlying = q.*&std::queue<int>::c; underlying.shrink_to_fit();
    주의: 이는 구현 세부사항에 의존하는 방법이므로 권장되지 않음
std::list를 사용할 경우 메모리 오버헤드를 고려해야 한다.
- 메모리 오버헤드란?
  - 각 노드마다 데이터 외에 두 개의 포인터(prev, next)를 저장
  - 노드 단위로 메모리를 할당하므로 각 노드마다 메모리 할당 오버헤드 발생
- 고려해야 하는 이유:
  - 데이터 크기가 작은 경우 포인터 크기가 전체 메모리 사용량의 상당 부분을 차지
  - 예: 4바이트 int 데이터의 경우, 32비트 시스템에서 8바이트(포인터 2개)의 추가 메모리 필요
  - 노드 단위 할당으로 인한 메모리 단편화 발생
  - 캐시 지역성(cache locality)이 떨어져 성능 저하 가능
- 최적화 전략:
  - 작은 크기의 데이터는 std::deque 사용 고려
  - 대량의 데이터를 한 번에 할당하는 경우 std::deque가 더 효율적
  - 메모리 단편화가 심한 경우 std::deque 사용 고려

7. 💡 실제 활용 예시

📝 너비 우선 탐색(BFS)

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>

void bfs(const std::vector<std::vector<int>>& graph, int start) {
    std::queue<int> q;
    std::unordered_set<int> visited;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        std::cout << "방문: " << current << "\n";
        
        // 인접 노드 탐색
        for (int neighbor : graph[current]) {
            if (visited.find(neighbor) == visited.end()) {
                q.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }
}

int main() {
    // 예시 그래프 (인접 리스트)
    std::vector<std::vector<int>> graph = {
        {1, 2},     // 0번 노드의 인접 노드
        {0, 3, 4},  // 1번 노드의 인접 노드
        {0, 5},     // 2번 노드의 인접 노드
        {1},        // 3번 노드의 인접 노드
        {1},        // 4번 노드의 인접 노드
        {2}         // 5번 노드의 인접 노드
    };
    
    bfs(graph, 0);  // 0번 노드부터 BFS 시작
    return 0;
}

🔄 프린터 큐 시뮬레이션

#include <iostream>
#include <queue>
#include <vector>

struct Document {
    int id;
    int priority;
    
    Document(int i, int p) : id(i), priority(p) {}
};

int simulatePrinterQueue(std::queue<Document>& q, int target_id) {
    int time = 0;
    
    while (!q.empty()) {
        Document current = q.front();
        q.pop();
        
        // 현재 문서보다 우선순위가 높은 문서가 있는지 확인
        bool has_higher_priority = false;
        std::queue<Document> temp = q;
        while (!temp.empty()) {
            if (temp.front().priority > current.priority) {
                has_higher_priority = true;
                break;
            }
            temp.pop();
        }
        
        if (has_higher_priority) {
            // 현재 문서를 다시 큐에 추가
            q.push(current);
        } else {
            // 현재 문서 출력
            time++;
            if (current.id == target_id) {
                return time;
            }
        }
    }
    
    return -1;  // 타겟 문서를 찾지 못한 경우
}

int main() {
    std::queue<Document> printer_queue;
    
    // 문서 추가 (id, priority)
    printer_queue.push(Document(0, 1));
    printer_queue.push(Document(1, 2));
    printer_queue.push(Document(2, 3));
    printer_queue.push(Document(3, 2));
    
    int target_id = 2;  // 찾고자 하는 문서의 ID
    int time = simulatePrinterQueue(printer_queue, target_id);
    
    std::cout << "문서 " << target_id << "가 " << time << "번째로 출력됩니다.\n";
    return 0;
}

8. 🎯 면접 대비 핵심 개념

📝 기본 개념 및 특징

Q1. `std::queue`란 무엇인가요? 어떤 자료구조를 기반으로 하나요?

A. std::queue는 FIFO(First In First Out) 원칙을 따르는 컨테이너 어댑터입니다.

주요 특징:
- FIFO 구조 (선입선출)
- 컨테이너 어댑터 (실제 컨테이너를 감싸는 래퍼)
- 기본적으로 std::deque 기반
- 제한된 인터페이스 (front, back, push, pop)
기반 컨테이너:
- 기본: std::deque
- 대안: std::list
- 요구사항: front(), back(), push_back(), pop_front() 지원

💡 주요 멤버 함수 및 사용법

Q2. `push()`와 `emplace()`의 차이점은 무엇인가요?

A. 두 함수는 요소 추가 방식이 다릅니다.

push():

객체를 생성한 후 큐에 복사/이동

복사 연산의 경우:

queue.push(MyClass(1, 2));  // 1. 임시 객체 생성
                            // 2. 복사 생성자로 큐에 추가 (깊은 복사)
                            // 3. 임시 객체 파괴 (원본 데이터 유지)

이동 연산의 경우:

queue.push(std::move(obj)); // 1. 임시 객체 생성
                            // 2. 이동 생성자로 큐에 추가 (리소스 이동)
                            // 3. 임시 객체 파괴 (이동된 객체는 유효하지만 비어있음)

emplace():
- 큐 내부에서 직접 객체 생성
- 생성자 인자만 전달하여 내부에서 직접 생성
- 임시 객체 생성/파괴 과정 없음
- 예시:
```
queue.emplace(1, 2);  // 생성자 인자만 전달하여 큐 내부에서 직접 생성
```

Q3. 큐의 반복자가 없는 이유는 무엇인가요?

A. 큐의 FIFO 특성 때문입니다.

설계 의도:
- FIFO 구조는 맨 앞과 맨 뒤 요소만 접근 가능
- 중간 요소 접근은 큐의 본질적인 특성 위배
- 반복자 제공 시 큐의 추상화가 깨질 수 있음

🔧 메모리 관리 및 성능

Q4. 큐의 기본 컨테이너로 `std::deque`를 선택한 이유는 무엇인가요?

A. std::deque가 큐 연산에 최적화되어 있기 때문입니다.

장점:
- 양쪽 끝에서 O(1) 시간에 삽입/삭제
- 재할당 없이 크기 조절 가능
- 메모리 블록이 분산되어 있어 큰 데이터 처리에 적합
다른 컨테이너와 비교:
- vector: 앞쪽 삭제가 O(n) 시간 소요
- list: 메모리 오버헤드가 큼

⚡ 성능 및 최적화

Q5. 큐의 성능을 최적화하는 방법은 무엇인가요?

A. 사용 사례에 따라 여러 방법이 있습니다.

컨테이너 선택:
- 일반적인 사용: std::deque (양쪽 끝 연산 최적화)
- 메모리 효율성: std::list (포인터 조작)
메모리 관리:
- 불필요한 복사/이동 연산 피하기
- emplace() 사용으로 임시 객체 생성 방지
- 대용량 데이터 처리 시 메모리 블록 크기 고려

📊 실제 활용

Q6. 큐의 일반적인 사용 사례는 무엇인가요?

A. 여러 알고리즘과 문제 해결에 활용됩니다.

일반적인 사용 사례:
- 너비 우선 탐색(BFS)
- 작업 스케줄링
- 프린터 큐
- 메시지 큐
- 이벤트 처리

Q7. 큐를 사용한 알고리즘의 시간 복잡도는 어떻게 되나요?

A. 기본 연산의 시간 복잡도는 다음과 같습니다.

기본 연산:
- push(): O(1)
- pop(): O(1)
- front(): O(1)
- back(): O(1)
- empty(): O(1)
- size(): O(1)
전체 알고리즘:
- n개 요소 처리: O(n)
- 각 요소당 상수 시간 연산

Q8. 선형 큐와 원형 큐의 차이점은 무엇인가요? 각각의 구현 방법은 어떻게 되나요?

A. 두 큐의 주요 차이점과 구현 방법은 다음과 같습니다:

선형 큐 (Linear Queue):

특징:
- 배열의 앞부분이 비어있어도 새로운 요소를 추가할 수 없음
- 데이터 이동이 필요하거나 메모리 낭비 발생
- 구현이 단순하지만 비효율적

구현 방법:

class LinearQueue {
    int* arr;
    int front, rear;
    int capacity;
        
public:
    LinearQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = rear = -1;
    }
        
    void enqueue(int x) {
        if (rear == capacity - 1) {
            // 큐가 가득 찬 경우
            if (front == -1) return;  // 진짜로 가득 참
                
            // 데이터 이동
            for (int i = front; i <= rear; i++) {
                arr[i - front] = arr[i];
            }
            rear = rear - front;
            front = 0;
        }
        if (front == -1) front = 0;
        arr[++rear] = x;
    }
        
    int dequeue() {
        if (front == -1) return -1;  // 큐가 비어있음
        int x = arr[front];
        if (front == rear) front = rear = -1;
        else front++;
        return x;
    }
};

원형 큐 (Circular Queue):

특징:
- 배열의 끝에 도달하면 다시 처음으로 돌아가서 공간 활용
- 메모리 효율성이 높음
- 데이터 이동이 필요 없음
- 구현이 약간 복잡하지만 효율적