[C언어/C++] STL queue 총정리 - 개념, 원리, 사용법, 예제코드, 시간복잡도, 주의사항, 예제코드, 코딩테스트 활용 예시

STL - Queue 사용법 총 정리

 

 

1. queue란?

queue(큐)는 FIFO(First In, First Out, 선입선출) 방식으로 동작하는 자료구조입니다. 먼저 들어온 데이터가 먼저 나가므로, 줄을 서는 대기열과 같은 구조를 가집니다.

반응형

 

 

2. queue의 원리

queue는 두 개의 주요 연산을 가집니다.

• push(): 데이터를 큐의 끝에 추가합니다.
• pop(): 큐의 앞(front)에 있는 데이터를 제거합니다.

이외에도 다음과 같은 주요 연산이 제공됩니다.

• front(): 큐의 가장 앞(front) 요소를 확인합니다.
• back(): 큐의 가장 뒤(back) 요소를 확인합니다.
• empty(): 큐가 비어있는지 확인합니다.
• size(): 큐의 크기를 반환합니다.

 

 

3. queue 사용법 정리

3.1. queue 선언 및 기본 사용법

#include <stdio.h>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    
    q.push(10);
    q.push(20);
    q.push(30);
    
    printf("Front: %d\n", q.front()); // 10
    printf("Back: %d\n", q.back()); // 30
    
    q.pop();
    printf("Front after pop: %d\n", q.front()); // 20
    
    return 0;
}

 

3.2. queue의 주요 연산 예제

#include <stdio.h>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    for (int i = 1; i <= 5; i++) {
        q.push(i * 10); // 10, 20, 30, 40, 50 삽입
    }
    
    printf("Queue size: %d\n", (int)q.size());
    
    while (!q.empty()) {
        printf("Front: %d\n", q.front());
        q.pop();
    }
    
    return 0;
}

 

 

3.3. queue를 활용한 다양한 예제

3.3.1. 문자열을 저장하는 queue

#include <stdio.h>
#include <queue>
#include <string>
using namespace std;

int main() {
    queue<string> q;
    
    q.push("Hello");
    q.push("World");
    q.push("Queue");
    
    while (!q.empty()) {
        printf("%s\n", q.front().c_str());
        q.pop();
    }
    
    return 0;
}

 

3.3.2. 구조체를 저장하는 queue

#include <stdio.h>
#include <queue>
using namespace std;

struct Person {
    int id;
    char name[20];
};

int main() {
    queue<Person> q;
    
    q.push({1, "Alice"});
    q.push({2, "Bob"});
    q.push({3, "Charlie"});
    
    while (!q.empty()) {
        Person p = q.front();
        printf("ID: %d, Name: %s\n", p.id, p.name);
        q.pop();
    }
    
    return 0;
}

 

 

 

 

4. queue의 시간 복잡도

연산	시간 복잡도
push()	O(1)
pop()	O(1)
front()	O(1)
back()	O(1)
empty()	O(1)
size()	O(1)

queue의 모든 연산은 상수 시간(O(1)) 에 수행되므로 매우 효율적입니다.

 

 

 

5. queue 사용 시 주의사항

1. 큐가 비어있을 때 front() 또는 pop()을 호출하면 오류가 발생할 수 있습니다.

   if (!q.empty()) {
       printf("Front: %d\n", q.front());
   }
   

2. 큐는 중간 삽입/삭제가 불가능합니다.
   • 큐의 중간 데이터를 수정하려면 다른 구조를 고려해야 합니다.

 

 

6. 코딩 테스트에서 queue 활용 패턴

6.1. BFS(너비 우선 탐색)에서 queue 활용

#include <stdio.h>
#include <queue>
using namespace std;

int visited[100] = {0};
int graph[100][100] = {0};

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        printf("Visit: %d\n", node);
        
        for (int i = 0; i < 100; i++) {
            if (graph[node][i] && !visited[i]) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
}

 

6.2. 최근 사용된 데이터 관리 (LRU 캐싱 등)

#include <stdio.h>
#include <queue>
using namespace std;

#define CACHE_SIZE 3

queue<int> cache;

void accessData(int data) {
    if (cache.size() == CACHE_SIZE) {
        cache.pop();
    }
    cache.push(data);
}

int main() {
    accessData(1);
    accessData(2);
    accessData(3);
    accessData(4); // 가장 오래된 데이터(1)가 제거됨
    
    while (!cache.empty()) {
        printf("Cache: %d\n", cache.front());
        cache.pop();
    }
    
    return 0;
}

 

 

7. 요약

• queue는 선입선출(FIFO) 방식을 따르는 기본적인 자료구조입니다.
• 모든 연산이 O(1) 시간 복잡도로 동작하여 빠릅니다.
• BFS, 캐싱, 프로세스 스케줄링 등 다양한 곳에서 활용됩니다.
• 중간 삽입/삭제가 필요하면 다른 구조를 고려해야 합니다.

 

 

함께 보면 좋은 글 - STL 사용법 총정리 시리즈

2025.02.22 - [STL] - [C언어/C++] STL Iterator 총정리 - 개념, 원리, 사용법, 시간복잡도, 코딩 테스트 활용법

[C언어/C++] STL Iterator 총정리 - 개념, 원리, 사용법, 시간복잡도, 코딩 테스트 활용법

2025.02.22 - [STL] - [C언어/C++] auto 키워드 완벽 정리 - 개념, 원리, 사용법, 예제, 주의사항

[C언어/C++] auto 키워드 완벽 정리 - 개념, 원리, 사용법, 예제, 주의사항