C++ 适配器 stack/queue/priority_queue 使用和实现

目录

1. 引言
2. 适配器概述
   • 2.1 什么是适配器
   • 2.2 适配器的特点
3. C++ STL 容器
   • 3.1 序列容器与关联容器
4. stack（栈）
   • 4.1 stack 的实现
   • 4.2 使用示例
   • 4.3 应用场景
5. queue（队列）
   • 5.1 queue 的实现
   • 5.2 使用示例
   • 5.3 应用场景
6. priority_queue（优先队列）
   • 6.1 priority_queue 的实现
   • 6.2 使用示例
   • 6.3 应用场景
7. 总结

引言

在现代 C++ 编程中，数据结构的选择对程序的效率和可读性至关重要。C++ 标准模板库 (STL) 提供了一系列适配器，包括 stack、queue 和 priority_queue，使得开发者能够以简洁的方式管理数据。本文将详细探讨这些适配器的使用和实现，并提供实际案例和应用场景。

适配器概述

什么是适配器

适配器是一种设计模式，它的目的是将一种接口转换成另一种接口，使得原本由于接口不兼容而无法一起工作的类可以一起工作。在 C++ 中，适配器主要指的是 STL 中的适配器容器，它们基于其他底层容器（如向量、链表等）提供特定的功能。

适配器的特点

• 封装性：适配器隐藏了底层容器的复杂性。
• 灵活性：可以灵活地更换底层容器。
• 简单易用：提供了更加高层次的操作接口。

C++ STL 容器

C++ STL 包含多种容器，主要分为两类：序列容器和关联容器。

序列容器与关联容器

• 序列容器：如 vector、deque、list，用于按顺序存储元素。
• 关联容器：如 set、map、unordered_set，用于根据键值对存储数据。

适配器通常基于序列容器构建，例如 stack 和 queue。

stack（栈）

stack 的实现

stack 是一种后进先出 (LIFO) 的数据结构，通常用于需要临时存储数据的场景。C++ STL 中的 stack 默认使用 deque 作为底层容器。

cppCopy Code
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << "栈顶元素: " << s.top() << std::endl; // 输出 3
    s.pop();
    std::cout << "栈顶元素: " << s.top() << std::endl; // 输出 2

    return 0;
}

使用示例

以下是一个计算表达式的例子，使用栈来存储操作数：

cppCopy Code
#include <iostream>
#include <stack>
#include <string>
#include <sstream>

int evaluateExpression(const std::string& expression) {
    std::stack<int> s;
    std::istringstream iss(expression);
    std::string token;

    while (iss >> token) {
        if (isdigit(token[0])) {
            s.push(std::stoi(token));
        } else {
            int right = s.top(); s.pop();
            int left = s.top(); s.pop();

            switch (token[0]) {
                case '+': s.push(left + right); break;
                case '-': s.push(left - right); break;
                case '*': s.push(left * right); break;
                case '/': s.push(left / right); break;
            }
        }
    }

    return s.top();
}

int main() {
    std::string expression = "3 4 + 2 * 7 /";
    std::cout << "结果: " << evaluateExpression(expression) << std::endl; // 输出 2
    return 0;
}

应用场景

1. 括号匹配：在编译器中检查括号是否匹配。
2. 深度优先搜索：在图遍历中使用栈保存访问状态。
3. 逆波兰表达式计算：进行算术表达式评估。

queue（队列）

queue 的实现

queue 是一种先进先出 (FIFO) 的数据结构，适合需要顺序处理数据的场景。C++ STL 中的 queue 默认使用 deque 作为底层容器。

cppCopy Code
#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << "队头元素: " << q.front() << std::endl; // 输出 1
    q.pop();
    std::cout << "队头元素: " << q.front() << std::endl; // 输出 2

    return 0;
}

使用示例

下面的例子展示了如何使用队列模拟银行排队系统：

cppCopy Code
#include <iostream>
#include <queue>
#include <string>

class Customer {
public:
    std::string name;
    int serviceTime;

    Customer(std::string n, int t) : name(n), serviceTime(t) {}
};

int main() {
    std::queue<Customer> bankQueue;

    bankQueue.push(Customer("Alice", 5));
    bankQueue.push(Customer("Bob", 3));
    bankQueue.push(Customer("Charlie", 2));

    while (!bankQueue.empty()) {
        Customer c = bankQueue.front();
        bankQueue.pop();
        std::cout << "为 " << c.name << " 服务，预计时间: " << c.serviceTime << " 分钟" << std::endl;
    }

    return 0;
}

应用场景

1. 任务调度：操作系统中的进程调度。
2. 广度优先搜索：在图遍历中使用队列保存访问状态。
3. 打印队列：管理打印任务的顺序执行。

priority_queue（优先队列）

priority_queue 的实现

priority_queue 是一种特殊的队列，其中每个元素都有一个优先级，具有最高优先级的元素最先被处理。C++ STL 中的 priority_queue 默认使用 vector 作为底层容器。

cppCopy Code
#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "优先队列的最大元素: " << pq.top() << std::endl; // 输出 30
    pq.pop();
    std::cout << "优先队列的最大元素: " << pq.top() << std::endl; // 输出 20

    return 0;
}

使用示例

以下示例展示了如何使用优先队列实现任务调度：

cppCopy Code
#include <iostream>
#include <queue>
#include <vector>

struct Task {
    int id;
    int priority;

    // 构造函数
    Task(int i, int p) : id(i), priority(p) {}

    // 运算符重载, 使得优先队列根据 priority 排序
    bool operator<(const Task& other) const {
        return priority < other.priority; // 优先级低的在后面
    }
};

int main() {
    std::priority_queue<Task> taskQueue;

    taskQueue.push(Task(1, 3));
    taskQueue.push(Task(2, 1));
    taskQueue.push(Task(3, 2));

    while (!taskQueue.empty()) {
        Task t = taskQueue.top();
        taskQueue.pop();
        std::cout << "处理任务 ID: " << t.id << "，优先级: " << t.priority << std::endl;
    }

    return 0;
}

应用场景

1. 任务调度：在操作系统中根据优先级调度任务。
2. 事件驱动模拟：根据事件优先级处理事件。
3. 图算法：如 Dijkstra 算法中的最短路径查找。

总结

在本文中，我们详细探讨了 C++ STL 中的适配器 stack、queue 和 priority_queue 的使用和实现。通过具体的代码示例和应用场景，展示了这些适配器如何帮助我们更有效地管理数据。适配器不仅提高了代码的可读性和可维护性，还提升了开发效率。希望本文能为读者在 C++ 编程中提供一些实用的参考和指导。