stack의 기본 컨테이너로 deque를 쓰는 이유는?

표준 기본이 deque인데, **양끝 연산**과 세그먼트 구조 덕에 vector와 다른 트레이드오프가 있습니다. 필요하면 stack에 vector를 명시할 수 있습니다.

BFS에 queue, DFS에 stack을 쓰는 이유는?

탐색 순서를 맞추기 위함입니다. 실제로는 **재귀**가 내부적으로 스택을 쓰므로 DFS를 재귀로도 구현합니다.

priority_queue는 어떤 힙인가요?

기본은 **최대 힙**이라 최댓값이 위에 옵니다. 최소 힙이 필요하면 비교자를 뒤집거나 greater를 씁니다.

queue에 vector를 밑에 두면 안 되는 경우는?

컨테이너가 queue 어댑터 요구를 만족해야 합니다. vector는 앞쪽 pop 비용이 커서 **deque가 기본**인 이유와 연결됩니다.

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

2024년 3월 18일 · 10분 읽기 · 수정 2026년 4월 7일 초급 튜토리얼

이 글의 핵심

C++ queue/stack의 C++, queue/stack, "자료구조", 자료구조 비교를 실전 예제와 함께 상세히 설명합니다.

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

자료구조 비교

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

stack 기본

std::stack은 원소를 넣은 순서의 역순으로 꺼내는 후입선출(LIFO) 자료구조로, 내부적으로는 원시 배열이나 연결 리스트를 직접 구현하는 대신 std::deque를 기본 컨테이너로 감싸는 컨테이너 어댑터(container adapter)로 구현되어 있습니다. push()로 맨 위에 원소를 쌓고, top()으로 맨 위 원소를 확인하고, pop()으로 맨 위 원소를 제거하는 세 가지 연산만으로 동작하는 단순한 인터페이스 덕분에, 함수 호출 스택 흉내나 괄호 짝 맞추기, 실행 취소(undo) 기능처럼 “가장 최근 것부터 처리해야 하는” 문제에 자연스럽게 들어맞습니다. 아래 예시는 push로 1, 2, 3을 순서대로 쌓은 뒤 top()과 pop()을 반복 호출하며 3, 2 순서로 값이 나오는 LIFO 동작을 직접 확인해 볼 수 있습니다.

#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 기본

std::queue는 stack과 반대로 넣은 순서 그대로 꺼내는 선입선출(FIFO) 자료구조로, 은행 창구 대기열이나 프린터 작업 대기열처럼 “먼저 온 것부터 먼저 처리해야 하는” 상황을 모델링하는 데 적합합니다. stack과 달리 양쪽 끝에 각각 다른 이름의 접근 함수가 있는데, push()는 뒤쪽(back)에 원소를 추가하고 front()는 맨 앞 원소를, back()은 맨 뒤 원소를 각각 확인할 수 있으며 pop()은 항상 맨 앞 원소를 제거합니다. 아래 예시에서 1, 2, 3을 순서대로 push한 뒤 front()를 확인하면 가장 먼저 넣은 1이 나오는 것을 볼 수 있고, 이는 뒤에서 다룰 BFS(너비 우선 탐색) 알고리즘이 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 기본

std::priority_queue는 삽입 순서와 무관하게 항상 가장 우선순위가 높은 원소가 맨 위에 오도록 유지되는 자료구조로, 내부적으로는 힙(heap) 자료구조로 구현되어 삽입과 삭제 모두 O(log n) 시간에 처리됩니다. 별도로 비교 기준을 지정하지 않으면 기본값은 최대 힙이라 가장 큰 값이 항상 top()에 오지만, 세 번째 템플릿 인자로 greater<int>를 지정하면 비교 방향이 뒤집혀 가장 작은 값이 top()에 오는 최소 힙으로 동작합니다. 아래 예시에서 3, 1, 5, 2를 순서 없이 넣어도 pop()을 반복할 때마다 5, 3, 2, 1처럼 항상 큰 값부터 나오는 것을 볼 수 있으며, 이런 특성 덕분에 다익스트라 최단 경로 알고리즘이나 작업 스케줄링처럼 “항상 가장 급한 것부터 처리해야 하는” 문제에 널리 쓰입니다.

#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;
}

실전 예시

stack과 queue의 진짜 활용 가치는 단순한 자료 저장을 넘어, 그래프나 트리를 탐색하는 알고리즘의 핵심 자료구조로 쓰일 때 드러납니다. 아래 세 가지 예시는 각각 stack 기반 DFS, queue 기반 BFS, priority_queue 기반 작업 스케줄링이라는 코딩 테스트와 실무 모두에서 자주 등장하는 패턴을 다룹니다.

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

깊이 우선 탐색은 한 방향으로 최대한 깊이 파고들다가 더 갈 곳이 없으면 되돌아오는 탐색 방식으로, stack의 LIFO 특성과 정확히 맞아떨어집니다. 아래 코드는 시작 노드를 stack에 넣고, stack에서 노드를 하나씩 꺼내며 아직 방문하지 않았다면 방문 처리를 하고 그 인접 노드들을 다시 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

너비 우선 탐색은 시작 노드에서 가까운 노드부터 한 단계씩 넓혀가며 탐색하는 방식으로, 이 순서를 정확히 지키려면 queue의 FIFO 특성이 필요합니다. 아래 코드는 큐에 {노드, 거리} 쌍을 넣어 시작 노드로부터의 거리를 함께 추적하면서, 먼저 큐에 들어온 노드(즉 더 가까운 노드)부터 처리하는 덕분에 목표 노드에 처음 도달했을 때의 거리가 항상 최단 거리임을 보장합니다. 만약 여기서 queue 대신 stack을 썼다면 깊이 우선으로 파고들어 최단 경로가 아닌 엉뚱한 경로를 먼저 찾아버렸을 것이므로, 이 예시는 자료구조 선택이 알고리즘의 정확성 자체를 좌우한다는 것을 잘 보여줍니다.

#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

우선순위가 다른 여러 작업을 처리 순서대로 관리해야 하는 스케줄러는 priority_queue를 활용하기에 이상적인 상황입니다. 아래 Task 구조체는 operator<를 오버로드해 priority 값이 높을수록 우선순위가 높다고 정의하고 있으며, 이 비교 연산자 덕분에 priority_queue<Task>에 작업을 순서 없이 넣어도 pop()을 반복할 때마다 항상 우선순위가 가장 높은 작업부터 꺼낼 수 있습니다. 커스텀 타입을 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로 우선순위 기반 스케줄링을 구현합니다. 작업 관리, 이벤트 처리에 활용됩니다.

자주 발생하는 문제

stack, queue, priority_queue는 컨테이너 어댑터라는 특성 때문에 std::vector나 std::deque에 익숙한 개발자가 처음 접하면 당황하기 쉬운 제약들이 있습니다. 아래 세 가지는 특히 초보자가 자주 마주치는 컴파일 에러와 그 해결법입니다.

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

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

원인: stack과 queue는 인덱스 접근을 지원하지 않음. 컨테이너 어댑터는 내부 컨테이너(기본적으로 deque)를 감싸서 의도적으로 제한된 인터페이스만 노출하도록 설계되었기 때문에, 순서를 지키지 않고 임의 위치에 접근하는 연산 자체를 애초에 허용하지 않습니다. 이는 실수가 아니라 “LIFO/FIFO 규칙을 어기는 접근을 원천적으로 막는다”는 설계 의도가 반영된 결과입니다.

해결법:

// ❌ 컴파일 에러
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 반환 (값을 반환하지 않음). 이는 표준 라이브러리 설계상 의도적인 선택인데, 만약 pop()이 값을 반환하면서 동시에 원소를 제거한다면 반환값을 복사하는 도중 예외가 발생했을 때 원소가 이미 제거되었는지 아닌지 애매한 상황이 생겨 예외 안전성을 보장하기 어려워지기 때문입니다. 그래서 표준 라이브러리는 “확인”(top)과 “제거”(pop)를 항상 별개의 연산으로 분리해 두었습니다.

해결법:

// ❌ 컴파일 에러
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< 또는 비교 함수 필요. priority_queue는 내부적으로 힙을 유지하기 위해 두 원소 중 어느 쪽이 더 “크다”고 볼 것인지 끊임없이 비교해야 하는데, int나 string처럼 표준 타입은 이미 < 연산자가 정의되어 있어 문제가 없지만 사용자 정의 구조체는 컴파일러가 두 값을 비교할 방법을 전혀 모르기 때문에 비교 기준을 직접 알려주어야 합니다.

해결법:

// ❌ 컴파일 에러
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 = [](const Person& a, const Person& b) {
    return a.age < b.age;
};

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

FAQ

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

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

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

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

C/C++ 예제 코드입니다.

#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++, queue, stack, 자료구조, BFS, DFS 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

이 글의 핵심

자료구조 비교

stack 기본

queue 기본

priority_queue 기본

실전 예시

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

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

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

자주 발생하는 문제

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

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

문제 3: priority_queue 커스텀 비교

FAQ

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

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

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

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

Q5: 성능은 어떤가요?

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

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

관련 글

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?