在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;
}