c++STL系列——（十）Adapter

当提到C++ STL（标准模板库）中的适配器（Adapter），我们通常指的是stack、queue和priority_queue这三种容器适配器。它们提供了对底层容器（如vector、deque或list）的封装，使得可以使用不同的接口来操作数据结构。本文将深入探讨C++ STL中的这三种适配器，包括其基本特性、用法以及实际应用。

stack：栈适配器

基本特性

栈是一种后进先出（LIFO）的数据结构，stack适配器提供了对底层容器的封装，并且只能从容器的一端进行插入和删除操作。

基本操作

入栈与出栈

std::stack<int> myStack;
myStack.push(1);  // 入栈
myStack.pop();    // 出栈

实际应用

括号匹配

在编译器实现中，栈广泛用于括号匹配的检查：

bool isParenthesesValid(const std::string& s) {
    std::stack<char> myStack;
    for (char c : s) {
        if (c == '(') {
            myStack.push(c);
        } else if (c == ')') {
            if (myStack.empty() || myStack.top() != '(') {
                return false;
            } else {
                myStack.pop();
            }
        }
    }
    return myStack.empty();
}

queue：队列适配器

基本特性

队列是一种先进先出（FIFO）的数据结构，queue适配器提供了对底层容器的封装，并且只能从容器的一端进行插入，另一端进行删除操作。

基本操作

入队与出队

std::queue<int> myQueue;
myQueue.push(1);  // 入队
myQueue.pop();    // 出队

实际应用

广度优先搜索（BFS）

在图论和树的遍历中，队列广泛用于实现BFS算法：

void bfs(std::vector<std::vector<int>>& graph, int start) {
    std::queue<int> q;
    std::vector<bool> visited(graph.size(), false);
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        // 处理当前节点node
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

priority_queue：优先队列适配器

基本特性

优先队列适配器提供了对底层容器的封装，并且在插入元素时会根据一定的优先级规则进行自动排序。

基本操作

插入元素与取出顶部元素

std::priority_queue<int> myPriorityQueue;
myPriorityQueue.push(3);  // 插入元素
int topElement = myPriorityQueue.top();  // 取出顶部元素
myPriorityQueue.pop();  // 移除顶部元素

实际应用

任务调度

在操作系统的任务调度中，优先队列广泛用于根据任务的优先级来安排执行顺序：

struct Task {
    int priority;
    // other information
};
struct Compare {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority;  // 定义优先级比较
    }
};
std::priority_queue<Task, std::vector<Task>, Compare> taskQueue;

总结

通过本文的介绍，你应该对C++ STL中的栈适配器stack、队列适配器queue和优先队列适配器priority_queue有了更加深入的了解。这三种适配器提供了方便的高层接口，使得我们能够更加轻松地操作数据结构，同时也能够应用到各种实际场景中。