[C++] STL 컨테이너 - Queue 큐

 

2025.02.17 - [C++] - [C++] STL 컨테이너 - Stack

[C++] STL 컨테이너 - Stack

 

• STL 컨테이너란?
  • Standard Template Library
  • 템플릿 기반으로 모든 컨테이너에 적용되는 표준 인터페이스
  • 메모리 자동관리 -> 메모리 단편화

---

💡 std::queue

• queue (큐) 란?
  • FIFO(First In, First Out)
  • 선입 선출 - 먼저 들어온 데이터가 먼저 나가는 구조
  • 배열과 달리 동적 크기 조절 가능
• 시간 복잡도 - O(1)

---

📍 queue 사용 예제

#include <iostream>
#include <queue>  // queue 라이브러리 포함

using namespace std;

int main() {
    queue<int> q;  // 정수형 큐 선언

    // 값 추가 (Push)
    q.push(10);
    q.push(20);
    q.push(30);

    cout << "Front element: " << q.front() << "\n";  // 10 출력
    cout << "Back element: " << q.back() << "\n";   // 30 출력

    // 값 삭제 (Pop)
    q.pop();  // 10 제거

    cout << "New front: " << q.front() << "\n";  // 20 출력

    return 0;
}

 

📍 queue의 주요 연산

함수	설명	시간복잡도
q.push(x)	큐의 맨 뒤에 x 삽입	O(1)
q.pop()	큐의 맨 앞 요소 제거	O(1)
q.front()	큐의 맨 앞 요소 반환	O(1)
q.back()	큐의 맨 뒤 요소 반환	O(1)
q.empty()	큐가 비어 있는지 확인 (true or false)	O(1)
q.size()	큐의 현재 크기 반환	O(1)

 

---

📌 Queue(큐) 활용 예제

 

1) 정수를 입력받아 FIFO 방식으로 출력하기

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;
    int n;

    cout << "Enter numbers (0 to stop): ";
    while (true) {
        cin >> n;
        if (n == 0) break;
        q.push(n);
    }

    cout << "FIFO order: ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

🔹 입력 예시: 1 2 3 4 5 0
🔹 출력 예시: 1 2 3 4 5

 

2) BFS (너비 우선 탐색) 구현

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

using namespace std;

void bfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int next : graph[node]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

int main() {
    int n = 6;  // 노드 개수
    vector<vector<int>> graph(n + 1);
    vector<bool> visited(n + 1, false);

    // 무방향 그래프 입력
    graph[1] = {2, 3};
    graph[2] = {4, 5};
    graph[3] = {6};
    graph[4] = {};
    graph[5] = {};
    graph[6] = {};

    cout << "BFS traversal: ";
    bfs(1, graph, visited);
    return 0;
}

🔹 출력 예시: 1 2 3 4 5 6

 

3) 프로세스 스케줄링 시뮬레이션 (FIFO 방식)

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<string> processQueue;

    // 프로세스 추가
    processQueue.push("Process A");
    processQueue.push("Process B");
    processQueue.push("Process C");

    // 실행
    while (!processQueue.empty()) {
        cout << "Executing: " << processQueue.front() << "\n";
        processQueue.pop();
    }

    return 0;
}

 

🔹 출력 예시:

Executing: Process A
Executing: Process B
Executing: Process C

---

 

 

📌  큐와 벡터(vector) & 스택(stack) 비교

자료구조	접근 방식	삽입/삭제	사용 목적
queue	FIFO (선입선출)	push(), pop() (O(1))	BFS, 프로세스 관리
stack	LIFO (후입선출)	push(), pop() (O(1))	DFS, 괄호 검사
vector	임의 접근 가능	push_back(), erase()	동적 배열, 정렬

 

---

✅ 큐를 활용하는 알고리즘

• BFS(너비 우선 탐색)
• 프로세스 스케줄링
• 캐시 구현 (LRU 캐시, FIFO 방식)
• 이벤트 처리 시스템
• 프린터 작업처리

---

 🪄 요약

 

• 큐(Queue)는 FIFO(First In, First Out) 구조를 가지는 자료구조
• C++에서는 <queue> 라이브러리를 사용하여 쉽게 구현 가능
• 시간 복잡도는 push, pop, front, back 모두 O(1)
• BFS, 프로세스 관리 등에 유용하게 활용됨