C++ Container Adapters | stack·queue

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

---

Container Adapter Overview

Comparison Table

Adapter	Data Structure	Insert	Delete	Access	Underlying Container
stack	LIFO	push	pop	top	deque (default)
queue	FIFO	push	pop	front/back	deque (default)
priority_queue	Heap	push	pop	top	vector (default)

---

Practical Implementation

1) stack (LIFO)

#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)

#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)

#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)

---

Related Articles

• C++ Algorithm Heap
• C++ Algorithm Numeric
• C++ Algorithm Remove Master container adapters for efficient C++ programming! 🚀

---

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. C++ container adapters complete guide.

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence. See the C++ series index for the full picture.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

---

Related Articles (Internal Links)

Other articles related to this topic.

• C++ Algorithm Heap | ‘힙 알고리즘’ 가이드
• C++ Algorithm Numeric | accumulate·reduce
• C++ Algorithm Remove | ‘제거 알고리즘’ 가이드

---

Keywords Covered in This Article (Related Search Terms)

This article covers C++, container, stack, queue, priority_queue, STL.