在C++中使用优先队列列表的示例

在C++中使用优先队列列表的示例

优先队列

优先队列 是一种容器适配器,特别设计为队列的第一个元素是队列中所有元素中最大的,并且元素按非递增顺序排列(因此我们可以看到队列的每个元素具有优先级{固定顺序})。

与优先队列一起使用的函数:

  • empty(): 此函数返回队列是否为空。
  • size(): 此函数返回队列的大小。
  • top(): 返回队列的顶部元素的引用。
  • push(x): 此函数在队列末尾添加元素“x”。

列表

列表 是可以进行非连续内存分配的序列容器。与向量相比,列表遍历较慢,但一旦找到位置,插入和删除很快。通常,当我们说一个列表时,我们谈论的是双向链接列表。为了实现单链表,我们使用前向列表。

与列表一起使用的函数:

  • push_front(x): 在列表开头添加新元素“x”。
  • push_back(x): 在列表末尾添加新元素“x”。

前向列表

前向列表 在STL中实现了单向链表。从C ++ 11开始,前向列表在插入,删除和移动操作(如排序)方面比其他容器更有用,并允许在常数时间内插入和删除元素。 它与列表的不同在于,前向列表仅跟踪下一个元素的位置,而列表则跟踪下一个和上一个元素的位置,从而增加存储每个元素所需的存储空间。前向列表的缺点是无法向后迭代,也无法直接访问其单个元素。

当仅需要正向遍历时(与单向链接列表优先于双向链接列表相同),可以优先使用前向列表,以节省空间。一些例子包括哈希中的链接,图的邻接列表表示等。

与前向列表一起使用的函数:

  • push_front(x): 在列表开头添加新元素“x”。

本文重点介绍了如何在C ++中使用前向列表和列表的优先队列。列表和前向列表的优先队列在设计复杂的数据结构时非常有用。

下面是前向列表的优先队列的实现:

// C++程序实现以上内容
#include <bits/stdc++.h>
using namespace std;
  
// 打印优先级队列内容,刻意进行值调用,
// 因为我们不想从优先级队列中删除元素
void print(priority_queue<forward_list<int> > priorityQueue)
{
    while (!priorityQueue.empty()) {
        // 优先级队列的每个元素本身都是一个forward list
        forward_list<int> st = priorityQueue.top();
  
        cout << "[ ";
  
        // 打印forward list的元素
        for (auto element : st)
            cout << element << ' ';
        cout << ']';
        cout << '\n';
  
        // 弹出最顶层forward list
        priorityQueue.pop();
    }
}
  
// 主函数
int main()
{
    // 声明一个forward list类型的优先级队列
    priority_queue<forward_list<int> > priorityQueue;
  
    // 声明一个forward list
    forward_list<int> forwardList1;
  
    // 将元素插入forward list
    forwardList1.push_front(2);
    forwardList1.push_front(4);
    forwardList1.push_front(6);
  
    // 将forward list插入优先级队列
    priorityQueue.push(forwardList1);
  
    // 声明另一个forward list
    forward_list<int> forwardList2;
  
    // 将元素插入forward list
    forwardList2.push_front(1);
    forwardList2.push_front(3);
    forwardList2.push_front(7);
  
    // 将forward list插入优先级队列
    priorityQueue.push(forwardList2);
  
    // 声明另一个forward list
    forward_list<int> forwardList3;
  
    // 将元素插入forward list
    forwardList3.push_front(11);
    forwardList3.push_front(22);
    forwardList3.push_front(33);
  
    // 将forward list插入优先级队列
    priorityQueue.push(forwardList3);
  
    // 调用打印函数
    print(priorityQueue);
  
    return 0;
}  

输出

[ 33 22 11 ]
[ 7 3 1 ]
[ 6 4 2 ]

下面是优先级队列的列表实现:

// C++程序实现
//上述方法
#include <bits/stdc++.h>
using namespace std;
  
// 打印优先队列的函数
// 内容。故意传递它
//按值调用,因为我们不想
//从优先队列中删除元素
void print(priority_queue<list<int>> priorityQueue)
{
    while (!priorityQueue.empty()) {
        //优先级的每个元素
        //队列本身是一个列表
        list<int> st = priorityQueue.top();
  
        cout<<" [ ";
  
        //打印列表元素
        for (auto element : st)
            cout<<element<<' ';
  
        cout<<']';
        cout<<'\n';
  
        //弹出最顶层的列表
        priorityQueue.pop();
    }
}
  
//主驱动程序
int main()
{
    //声明一个优先加入列表的队列
    priority_queue<list<int>> priorityQueue;
  
    //声明一个列表
    list<int> list1;
  
    //插入列表
    //在前面推送
    list1.push_front(2);
  
    //在后面推入
    list1.push_back(4);
    list1.push_back(6);
  
    //将列表插入
    //优先队列
    priorityQueue.push(list1);
  
    //再次声明一个列表
    list<int> list2;
  
    //插入列表
    //在前面推送
    list2.push_front(2);
  
    //在后面推入
    list2.push_back(4);
    list2.push_back(7);
  
    //将列表插入
    //优先队列
    priorityQueue.push(list2);
  
    //再次声明一个列表
    list<int> list3;
  
    //插入列表
  
    //在前面推送
    list3.push_front(11);
  
    //在后面推入
    list3.push_back(22);
    list3.push_back(33);
  
    //将列表插入
    //优先队列
    priorityQueue.push(list3);
  
    //调用打印函数
    print(priorityQueue);
  
    return 0;
}  

输出

[ 11 22 33 ]
[ 2 4 7 ]
[ 2 4 6 ]

默认情况下,优先队列是最大堆,因此对于优先队列中的两个列表/前向列表,具有更大的第一个元素的列表/前向列表是最顶部的元素。如果第一个元素相等,则比较列表/前向列表的第二个值,依此类推。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 教程