C++ 容器类 <queue>

C++ 标准库中的 <queue> 头文件提供了队列（Queue）数据结构的实现。队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。

队列是一种线性数据结构，它遵循以下规则：

• 元素只能从队尾添加。
• 元素只能从队首移除。

语法

在 C++ 中，队列的语法如下：

#include <queue>

// 声明队列
std::queue<Type> q;

这里 Type 是队列中存储元素的数据类型。

常用操作

队列提供了以下常用操作：

• empty(): 检查队列是否为空。
• size(): 返回队列中的元素数量。
• front(): 返回队首元素的引用。
• back(): 返回队尾元素的引用。
• push(): 在队尾添加一个元素。
• pop(): 移除队首元素。

示例：

#include <iostream>
#include <queue>

int main() {
    // 创建一个整数队列
    std::queue<int> q;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 打印队列中的元素数量
    std::cout << "队列中的元素数量: " << q.size() << std::endl;

    // 打印队首元素
    std::cout << "队首元素: " << q.front() << std::endl;

    // 打印队尾元素
    std::cout << "队尾元素: " << q.back() << std::endl;

    // 移除队首元素
    q.pop();
    std::cout << "移除队首元素后，队首元素: " << q.front() << std::endl;

    // 再次打印队列中的元素数量
    std::cout << "队列中的元素数量: " << q.size() << std::endl;

    return 0;
}

输出：

队列中的元素数量: 3
队首元素: 10
队尾元素: 30
移除队首元素后，队首元素: 20
队列中的元素数量: 2

C++ 的 <queue> 标准库提供了一种方便的方式来实现队列数据结构。通过使用队列，我们可以有效地管理需要按照特定顺序处理的元素集合。希望这篇文章能帮助初学者更好地理解和使用 C++ 中的队列。

C++ 标准库 <deque>

在 C++中，<deque> 是标准模板库（STL）的一部分，它提供了双端队列（double-ended queue）的实现。

双端队列是一种允许在两端进行插入和删除操作的线性数据结构。

<deque> 的全称是 "double-ended queue"，它在C++中以模板类的形式存在，允许存储任意类型的数据。

<deque> 是一个动态数组，它提供了快速的随机访问能力，同时允许在两端进行高效的插入和删除操作。这使得 <deque> 成为处理需要频繁插入和删除元素的场景的理想选择。

语法

在 C++ 中，使用 <deque> 需要包含头文件 #include <deque>。以下是 <deque> 的基本语法：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque; // 创建一个整数类型的双端队列
    // 接下来可以进行插入、删除等操作
    return 0;
}

常用操作

下面是 std::deque 容器的一些常用成员函数：

示例：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> myDeque;

    // 插入元素
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_front(5);

    // 访问元素
    std::cout << "Deque contains: ";
    for (int i = 0; i < myDeque.size(); ++i) {
        std::cout << myDeque[i] << " ";
    }
    std::cout << std::endl;

    // 删除元素
    myDeque.pop_back();
    myDeque.pop_front();

    // 再次访问元素
    std::cout << "Deque after popping: ";
    for (int i = 0; i < myDeque.size(); ++i) {
        std::cout << myDeque[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出：

Deque contains: 5 10 20 
Deque after popping: 10 

在不知道 deque 长度的时候，可以使用 deque.front() 与 deque.back() 来访问头尾元素：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d;

    // 向双端队列中添加元素
    d.push_back(10);
    d.push_back(20);
    d.push_front(5);

    // 访问前端元素
    std::cout << "Front element: " << d.front() << std::endl;

    // 访问后端元素
    std::cout << "Back element: " << d.back() << std::endl;

    // 修改前端元素
    d.front() = 15;

    // 修改后端元素
    d.back() = 25;

    // 再次访问元素
    std::cout << "Modified front element: " << d.front() << std::endl;
    std::cout << "Modified back element: " << d.back() << std::endl;

    return 0;
}

输出：

Front element: 5
Back element: 20
Modified front element: 15
Modified back element: 25

C++ 容器类 <priority_queue>

在 C++ 中，<priority_queue> 是标准模板库（STL）的一部分，用于实现优先队列。

优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。

在 C++ 中，priority_queue 默认是一个最大堆，这意味着队列的顶部元素总是具有最大的值。

priority_queue 是一个容器适配器，它提供了对底层容器的堆操作。它不提供迭代器，也不支持随机访问。

语法

以下是 priority_queue 的基本语法：

#include <queue>

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
priority_queue<int, vector<int>, compare> pq_min;

常用操作

• empty(): 检查队列是否为空。
• size(): 返回队列中的元素数量。
• top(): 返回队列顶部的元素（不删除它）。
• push(): 向队列添加一个元素。
• pop(): 移除队列顶部的元素。

实例

下面是一个使用 priority_queue 的简单实例，我们将创建一个最大堆，并展示如何添加元素和获取队列顶部的元素。

#include <iostream>
#include <queue>

int main() {
    // 创建一个整型优先队列
    std::priority_queue<int> pq;

    // 向优先队列中添加元素
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // 输出队列中的元素
    std::cout << "队列中的元素：" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

输出结果：

队列中的元素：
50
30
20
10

自定义优先级

如果你需要一个最小堆，可以通过自定义比较函数来实现：

#include <iostream>
#include <queue>
#include <vector>

struct compare {
    bool operator()(int a, int b) {
        return a > b; // 定义最小堆
    }
};

int main() {
    // 创建一个自定义类型的优先队列，使用最小堆
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // 向优先队列中添加元素
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // 输出队列中的元素
    std::cout << "最小堆中的元素：" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

输出结果：

最小堆中的元素：
10
20
30
50

<priority_queue> 是C++ STL中一个非常有用的容器，特别适合需要快速访问最高或最低优先级元素的场景。通过自定义比较函数，我们可以轻松地实现最大堆或最小堆。希望这篇文章能帮助初学者更好地理解和使用 priority_queue。