
#include <iostream>
#include <queue>
 
using namespace std;
 
int main() {
    // 定义一个队列
    queue<int> q;
 
    // push(x): 将元素 x 插入到队列的末尾
    q.push(1);
    q.push(2);
    q.push(3);
 
    // pop(): 删除队列的第一个元素
    q.pop();
 
    // front(): 返回队列的第一个元素的引用
    cout << "Front element: " << q.front() << endl;
 
    // back(): 返回队列的最后一个元素的引用
    cout << "Back element: " << q.back() << endl;
 
    // size(): 返回队列中元素的个数
    cout << "Size of queue: " << q.size() << endl;
 
    // empty(): 判断队列是否为空
    if (q.empty()) {
        cout << "Queue is empty" << endl;
    } else {
        cout << "Queue is not empty" << endl;
    }
 
    return 0;
}

二、priority_queue

1、大根堆与小跟堆介绍

大根堆（max heap）：在大根堆中，父节点的值始终大于或等于其子节点的值。因此，大根堆的堆顶元素是整个堆中的最大值。其实就是一个类似完全二叉搜索树的结构，调用函数top()调用最上层节点，然后大根堆最上层节点是整颗树的最大值。

如下图：

小根堆（min heap）：在小根堆中，父节点的值始终小于或等于其子节点的值。因此，小根堆的堆顶元素是整个堆中的最小值。其他与大根堆类似，只不过小根堆上层是整颗树最小值

如下图：

2、priority_queue主要操作：

push(x): 将元素 x 插入到优先队列中
pop(): 删除优先队列中具有最高优先级的元素
top(): 返回优先队列中具有最高优先级的元素的引用
size(): 返回优先队列中元素的个数
empty(): 判断优先队列是否为空

这个push操作有一个上滤和下滤的过程，感兴趣的同学可以看b站：https://www.bilibili.com/video/BV1AF411G7cA/?spm_id_from=333.337.search-card.all.click&vd_source=c0734847af5a3708839a9c8fde15f6c53

https://www.bilibili.com/video/BV1AF411G7cA/?spm_id_from=333.337.search-card.all.click&vd_source=c0734847af5a3708839a9c8fde15f6c53

3、 C++ STL 中的 priority_queue 实现上述操作的示例代码:


#include <iostream>
#include <queue>
 
using namespace std;
 
int main() {
    // 定义一个小根堆的优先队列
    priority_queue<int, vector<int>, greater<int>> pq;
    // 需要大根堆的话这样定义
    priority_queue<int, vector<int>, less<int>> pq1;    
 
    // push(x): 将元素 x 插入到优先队列中
    pq.push(3);
    pq.push(1);
    pq.push(5);
 
    // pop(): 删除优先队列中具有最高优先级的元素
    pq.pop();
 
    // top(): 返回优先队列中具有最高优先级的元素的引用
    cout << "Top element: " << pq.top() << endl;
 
    // size(): 返回优先队列中元素的个数
    cout << "Size of priority queue: " << pq.size() << endl;
 
    // empty(): 判断优先队列是否为空
    if (pq.empty()) {
        cout << "Priority queue is empty" << endl;
    } else {
        cout << "Priority queue is not empty" << endl;
    }
 
    return 0;
}

三、deque

deque（double-ended queue）是一种具有两端插入和删除操作的数据结构，它允许在队列的两端高效地进行元素的插入和删除操作。deque可以在头部和尾部同时进行插入和删除操作，因此它既可以像栈一样后进先出，也可以像队列一样先进先出。

1、deque的操作：

创建 deque 对象：使用 deque<T>` 声明一个 deque，其中 `T` 是你想要存储的元素类型。

在两端插入元素：使用 `push_back(value)` 在 deque 的尾部插入元素，并使用 `push_front(value)` 在头部插入元素。

访问元素：使用 `front()` 获取 deque 的头部元素，使用 `back()` 获取尾部元素。

获取大小：使用 `size()` 获取 deque 的大小。

迭代器访问：使用迭代器（例如 `begin()` 和 `end()`）来迭代访问 deque 中的元素。

清空 deque：使用 clear()` 方法清空 deque 中的所有元素。

检查 deque 是否为空：使用 `empty()` 方法检查 deque 是否为空。

插入元素到指定位置：使用 `insert(position, value)` 在指定位置插入元素。

删除指定位置的元素：使用 `erase(position)` 删除指定位置的元素。

2、deque完整操作代码：


#include <iostream>
#include <deque>
 
using namespace std; // 使用命名空间std
 
int main() {
    // 创建一个整数类型的 deque
    deque<int> myDeque;
 
    // 在尾部插入元素
    myDeque.push_back(10);
    // 在头部插入元素
    myDeque.push_front(20);
 
    // 获取头部元素
    int frontElement = myDeque.front();
    // 获取尾部元素
    int backElement = myDeque.back();
 
    // 获取 deque 大小
    size_t size = myDeque.size();
 
    // 随机访问元素
    int value = myDeque[1]; // 索引从 0 开始
 
    // 使用迭代器访问元素
    for (auto it = myDeque.begin(); it != myDeque.end(); ++it) {
        cout << *it << " "; // 输出每个元素
    }
    cout << endl;
 
    // 清空 deque
    myDeque.clear();
 
    // 判断 deque 是否为空
    bool isEmpty = myDeque.empty();
 
    // 在指定位置插入元素
    auto it = myDeque.begin() + 1;
    myDeque.insert(it, 30);
 
    // 删除指定位置的元素
    it = myDeque.begin(); // 重新设置迭代器
    myDeque.erase(it + 1); // 删除第二个元素
 
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/707049