Previous
Next
C++ Container Adapters | stack·queue

C++ Container Adapters | stack·queue

· 28분 읽기 · 수정 Beginner Tutorial
C++ Container Adapters | stack·queue

이 글의 핵심

C++ container adapters stack (LIFO), queue (FIFO), priority_queue (heap) usage and practical application. Covers DFS·BFS·Dijkstra algorithm implementation, bracket validation, and task scheduling examples.

Introduction

C++ container adapters are existing containers wrapped with specific interfaces. There are three: stack (LIFO), queue (FIFO), priority_queue (heap). As an analogy, stack is like stacking plates (last placed is removed first), queue is like standing in line (first person in line goes first), priority_queue is like emergency room (person with highest priority gets treated first).

What You’ll Learn

  • Understand usage of stack, queue, priority_queue
  • Grasp time complexity of each adapter
  • Implement DFS, BFS, Dijkstra algorithms
  • Check practical usage patterns and precautions

Reality in Production

When learning development, everything is clean and theoretical. But production is different. You wrestle with legacy code, chase tight deadlines, and face unexpected bugs. The content covered in this guide was initially learned as theory, but I realized “ah, that’s why it’s designed this way” while applying it to actual projects. What stands out in my memory is the trial and error from my first project. I did it as I learned from books but spent days not knowing why it didn’t work. Eventually, I found the problem through a senior developer’s code review and learned a lot in the process. This guide covers not only theory but also pitfalls you may encounter in practice and their solutions.

Container Adapter Overview

Comparison Table

AdapterData StructureInsertDeleteAccessUnderlying Container
stackLIFOpushpoptopdeque (default)
queueFIFOpushpopfront/backdeque (default)
priority_queueHeappushpoptopvector (default)

Practical Implementation

1) stack (LIFO)

Here is detailed implementation code using C++. Import the necessary modules and process data with loops. Understand the role of each part while examining the code.

#include <iostream>
#include <stack>
int main() {
    std::stack<int> s;
    
    // push
    s.push(1);
    s.push(2);
    s.push(3);
    
    // top
    std::cout << s.top() << std::endl;  // 3
    
    // pop
    s.pop();
    std::cout << s.top() << std::endl;  // 2
    
    // size
    std::cout << s.size() << std::endl;  // 2
    
    // empty
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;  // 2 1
    
    return 0;
}

2) queue (FIFO)

Here is detailed implementation code using C++. Import the necessary modules and process data with loops. Understand the role of each part while examining the code.

#include <iostream>
#include <queue>
int main() {
    std::queue<int> q;
    
    // push
    q.push(1);
    q.push(2);
    q.push(3);
    
    // front/back
    std::cout << q.front() << std::endl;  // 1
    std::cout << q.back() << std::endl;   // 3
    
    // pop
    q.pop();
    std::cout << q.front() << std::endl;  // 2
    
    // size
    std::cout << q.size() << std::endl;  // 2
    
    // empty
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;  // 2 3
    
    return 0;
}

3) priority_queue (Heap)

Here is detailed implementation code using C++. Import the necessary modules and process data with loops. Understand the role of each part while examining the code.

#include <iostream>
#include <queue>
#include <vector>
int main() {
    // Max heap (default)
    std::priority_queue<int> maxHeap;
    
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(2);
    
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";  // 4 3 2 1
        maxHeap.pop();
    }
    std::cout << std::endl;
    
    // Min heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(2);
    
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";  // 1 2 3 4
        minHeap.pop();
    }
    std::cout << std::endl;
    
    return 0;
}

Summary

Key Points

  1. stack: LIFO (Last In First Out)
  2. queue: FIFO (First In First Out)
  3. priority_queue: Heap-based priority queue
  4. Time complexity: stack/queue O(1), priority_queue O(log n)
  5. No iterators: Adapters don’t provide iterators

When to Use

✅ Use stack when:

  • DFS (Depth-First Search)
  • Bracket/parenthesis validation
  • Undo/redo functionality
  • Expression evaluation ✅ Use queue when:
  • BFS (Breadth-First Search)
  • Task queue
  • Message queue
  • Level-order traversal ✅ Use priority_queue when:
  • Dijkstra’s algorithm
  • Task scheduling by priority
  • Event simulation
  • Top K elements

Best Practices

  • ✅ Check empty() before top()/front()
  • ✅ Use appropriate underlying container
  • ✅ Use custom comparator for priority_queue
  • ❌ Don’t access by index (no random access)
  • ❌ Don’t iterate (no iterators provided)

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. C++ container adapters complete guide. Usage and practical application of stack (LIFO), queue (FIFO), priority_queue (he… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

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

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

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

C++, container, stack, queue, priority_queue, STL 등으로 검색하시면 이 글이 도움이 됩니다.