C++ queue/stack | "자료구조" 완벽 정리 [BFS/DFS 활용]

· 10분 읽기 · 수정 초급 튜토리얼
C++ queue/stack | "자료구조" 완벽 정리 [BFS/DFS 활용]

이 글의 핵심

C++ queue/stack에 대한 실전 가이드입니다.

LIFO·FIFO 개념과 코딩 테스트에서의 쓰임은 알고리즘 시리즈: 스택과 큐와 맞물려 있습니다.

자료구조 비교

특성stackqueuepriority_queue
순서LIFO (후입선출)FIFO (선입선출)우선순위
접근top()front(), back()top()
삽입push()push()push()
삭제pop()pop()pop()

stack 기본

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> s;
    
    // 삽입
    s.push(1);
    s.push(2);
    s.push(3);
    
    // 맨 위 확인
    cout << s.top() << endl;  // 3
    
    // 제거
    s.pop();  // 3 제거
    cout << s.top() << endl;  // 2
    
    // 크기
    cout << s.size() << endl;
    
    // 비어있는지
    if (s.empty()) {
        cout << "비어있음" << endl;
    }
    
    return 0;
}

queue 기본

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    
    // 삽입
    q.push(1);
    q.push(2);
    q.push(3);
    
    // 앞/뒤 확인
    cout << q.front() << endl;  // 1
    cout << q.back() << endl;   // 3
    
    // 제거
    q.pop();  // 1 제거
    cout << q.front() << endl;  // 2
    
    return 0;
}

priority_queue 기본

#include <queue>
#include <iostream>
using namespace std;

int main() {
    // 기본: 최대 힙 (큰 값이 top)
    priority_queue<int> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(5);
    pq.push(2);
    
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 5 3 2 1
        pq.pop();
    }
    
    // 최소 힙 (작은 값이 top)
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(5);
    
    cout << "\n최소 힙: " << minHeap.top();  // 1
    
    return 0;
}

실전 예시

예시 1: DFS (깊이 우선 탐색) - stack

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

void dfs(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> s;
    
    s.push(start);
    
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        
        if (visited[node]) continue;
        
        visited[node] = true;
        cout << node << " ";
        
        // 인접 노드를 스택에 추가
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                s.push(neighbor);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},    // 0의 인접 노드
        {0, 3, 4}, // 1의 인접 노드
        {0, 4},    // 2의 인접 노드
        {1},       // 3의 인접 노드
        {1, 2}     // 4의 인접 노드
    };
    
    cout << "DFS: ";
    dfs(0, graph);
    
    return 0;
}

설명: stack을 사용한 DFS 구현입니다. 깊이 우선으로 탐색하며, 백트래킹 문제에 자주 사용됩니다.

예시 2: BFS (너비 우선 탐색) - queue

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int bfs(vector<vector<int>>& graph, int start, int target) {
    vector<bool> visited(graph.size(), false);
    queue<pair<int, int>> q;  // {노드, 거리}
    
    q.push({start, 0});
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front().first;
        int dist = q.front().second;
        q.pop();
        
        if (node == target) {
            return dist;  // 최단 거리 반환
        }
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push({neighbor, dist + 1});
            }
        }
    }
    
    return -1;  // 도달 불가
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 4},
        {1},
        {1, 2}
    };
    
    int distance = bfs(graph, 0, 3);
    cout << "0에서 3까지 최단 거리: " << distance << endl;
    
    return 0;
}

설명: queue를 사용한 BFS로 최단 경로를 찾습니다. 미로 찾기, 최단 거리 문제에 필수입니다.

예시 3: 작업 스케줄링 - priority_queue

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct Task {
    string name;
    int priority;
    int duration;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 높은 우선순위가 먼저
    }
};

int main() {
    priority_queue<Task> tasks;
    
    tasks.push({"이메일 확인", 2, 10});
    tasks.push({"긴급 회의", 5, 60});
    tasks.push({"코드 리뷰", 3, 30});
    tasks.push({"점심 식사", 1, 60});
    tasks.push({"버그 수정", 4, 120});
    
    cout << "=== 작업 실행 순서 ===" << endl;
    int totalTime = 0;
    
    while (!tasks.empty()) {
        Task t = tasks.top();
        tasks.pop();
        
        cout << t.priority << ". " << t.name 
             << " (" << t.duration << "분)" << endl;
        totalTime += t.duration;
    }
    
    cout << "\n총 소요 시간: " << totalTime << "분" << endl;
    
    return 0;
}

설명: priority_queue로 우선순위 기반 스케줄링을 구현합니다. 작업 관리, 이벤트 처리에 활용됩니다.

자주 발생하는 문제

문제 1: stack/queue에서 직접 접근 불가

증상: stack[0] 또는 queue[1] 같은 접근 시 컴파일 에러

원인: stack과 queue는 인덱스 접근을 지원하지 않음

해결법:

// ❌ 컴파일 에러
stack<int> s;
s.push(1);
s.push(2);
cout << s[0];  // 에러!

// ✅ 방법 1: 모두 꺼내서 확인
stack<int> s;
s.push(1);
s.push(2);
s.push(3);

while (!s.empty()) {
    cout << s.top() << " ";
    s.pop();
}

// ✅ 방법 2: vector 사용
vector<int> v = {1, 2, 3};
cout << v[0];  // OK

// ✅ 방법 3: deque 사용 (양쪽 접근 가능)
#include <deque>
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
cout << dq[0];  // OK
cout << dq.front();  // OK
cout << dq.back();   // OK

문제 2: pop()은 값을 반환하지 않음

증상: int x = s.pop(); 같은 코드가 컴파일 에러

원인: pop()은 void 반환 (값을 반환하지 않음)

해결법:

// ❌ 컴파일 에러
stack<int> s;
s.push(10);
int x = s.pop();  // 에러! pop()은 void

// ✅ 올바른 코드
stack<int> s;
s.push(10);
int x = s.top();  // 값 확인
s.pop();          // 제거

// ✅ 한 줄로
int x = s.top(); s.pop();

// ✅ 헬퍼 함수
template<typename T>
T pop_value(stack<T>& s) {
    T value = s.top();
    s.pop();
    return value;
}

int x = pop_value(s);  // OK

문제 3: priority_queue 커스텀 비교

증상: 커스텀 타입을 priority_queue에 넣으면 에러

원인: operator< 또는 비교 함수 필요

해결법:

// ❌ 컴파일 에러
struct Person {
    string name;
    int age;
};

priority_queue<Person> pq;  // 에러!

// ✅ 방법 1: operator< 정의
struct Person {
    string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;  // 나이 많은 사람이 우선
    }
};

priority_queue<Person> pq;  // OK

// ✅ 방법 2: 비교 함수
struct PersonCompare {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};

priority_queue<Person, vector<Person>, PersonCompare> pq;  // OK

// ✅ 방법 3: 람다 (복잡함)
auto cmp =  {
    return a.age < b.age;
};

priority_queue<Person, vector<Person>, decltype(cmp)> pq(cmp);

FAQ

Q1: stack과 queue는 언제 사용하나요?

A:

  • stack: 되돌리기(undo), 괄호 매칭, DFS, 함수 호출 스택
  • queue: BFS, 프린터 대기열, 작업 큐, 버퍼
  • priority_queue: 최단 경로(다익스트라), 작업 스케줄링, 힙 정렬

Q2: deque는 언제 사용하나요?

A: 양쪽에서 삽입/삭제가 필요할 때 사용합니다.

#include <deque>
deque<int> dq;

dq.push_front(1);  // 앞에 추가
dq.push_back(2);   // 뒤에 추가
dq.pop_front();    // 앞에서 제거
dq.pop_back();     // 뒤에서 제거

Q3: 최소 힙을 어떻게 만드나요?

A: greater를 사용합니다.

// 최대 힙 (기본)
priority_queue<int> maxHeap;

// 최소 힙
priority_queue<int, vector<int>, greater<int>> minHeap;

Q4: stack/queue의 크기를 미리 정할 수 있나요?

A: 아니요, 동적으로 크기가 조절됩니다. 고정 크기가 필요하면 배열이나 vector를 사용하세요.

Q5: 성능은 어떤가요?

A: 모든 연산이 O(1)입니다 (priority_queue는 O(log n)).

Q6: 여러 스레드에서 안전한가요?

A: 아니요, 멀티스레드 환경에서는 mutex로 보호해야 합니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

  • C++ 컨테이너 어댑터 | “stack/queue/priority_queue” 가이드
  • C++ 자료구조 | “직접 구현하기” 연결리스트/트리/해시테이블
  • C++ Stack Overflow | “스택 오버플로우” 가이드

관련 글

  • C++ 시리즈 전체 보기
  • C++ Adapter Pattern 완벽 가이드 | 인터페이스 변환과 호환성
  • C++ ADL |
  • C++ Aggregate Initialization |