实现优先队列

C++C++Beginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

在本实验中,我们将学习 C++ 编程语言中优先队列(Priority Queue)的基本功能。优先队列是 C++ STL(标准模板库,Standard Template Library)中的一个容器,它允许你根据元素的优先级插入和移除元素。优先级最高的元素始终位于队列的前端。当从队列中移除一个元素时,优先队列会自动将下一个优先级最高的元素插入到正确的位置。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/IOandFileHandlingGroup(["`I/O and File Handling`"]) cpp(("`C++`")) -.-> cpp/StandardLibraryGroup(["`Standard Library`"]) cpp(("`C++`")) -.-> cpp/SyntaxandStyleGroup(["`Syntax and Style`"]) cpp/ControlFlowGroup -.-> cpp/for_loop("`For Loop`") cpp/ControlFlowGroup -.-> cpp/while_loop("`While Loop`") cpp/IOandFileHandlingGroup -.-> cpp/output("`Output`") cpp/StandardLibraryGroup -.-> cpp/standard_containers("`Standard Containers`") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("`Code Formatting`") subgraph Lab Skills cpp/for_loop -.-> lab-96225{{"`实现优先队列`"}} cpp/while_loop -.-> lab-96225{{"`实现优先队列`"}} cpp/output -.-> lab-96225{{"`实现优先队列`"}} cpp/standard_containers -.-> lab-96225{{"`实现优先队列`"}} cpp/code_formatting -.-> lab-96225{{"`实现优先队列`"}} end

包含所需的库

我们将在 ~/project 目录下使用以下命令创建一个名为 main.cpp 的新文件:

touch ~/project/main.cpp

首先,我们需要包含程序正常运行所需的库。在本程序中,我们将使用 iostreambits/stdc++.h 库。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

定义 show 函数

show 函数用于显示优先队列中的所有元素。该函数以优先队列对象作为参数,并将队列复制到另一个队列中以保持原始优先队列不变。然后,通过遍历队列打印出优先队列中的所有元素。

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top(); //打印最顶部的元素
        pq.pop();                 //删除最顶部的元素以移动到下一个
    }
    cout << endl;
}

实现主函数

main 函数是所有操作发生的地方。我们首先声明一个整数变量 i,然后创建一个名为 q 的整数优先队列。接着,我们使用 push 函数向优先队列中添加一些整数。

之后,我们使用 show 函数显示优先队列中的元素。然后,我们使用 size 函数显示队列中元素的数量,并使用 top 函数显示优先级最高的元素。

接下来,我们使用 pop 函数移除优先级最高的元素,并使用 show 函数显示更新后的优先队列。

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

完整代码

你可以使用以下代码在 C++ 中实现优先队列:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void show(priority_queue<int> q)
{
    priority_queue<int> pq = q;
    while (!pq.empty())
    {
        cout << "\t" << pq.top();
        pq.pop();
    }
    cout << endl;
}

int main()
{
    priority_queue<int> q;

    for (int i = 1; i < 6; i++)
    {
        q.push(i * 10);
    }

    cout << "The Priority Queue is: ";
    show(q);

    cout << "\n\nThe number of elements in the Priority Queue are: " << q.size();

    cout << "\n\nThe element with the highest priority is: " << q.top();

    q.pop();
    cout << "\n\nAfter Deleting the top most element, Priority Queue becomes: ";
    show(q);

    return 0;
}

将上述代码保存到 ~/project/main.cpp 中。要编译并运行此代码,请使用以下命令:

g++ main.cpp -o main && ./main

总结

在本实验中,我们学习了 C++ 中优先队列(Priority Queue)的基本概念。我们还了解了如何声明和初始化优先队列,以及如何添加、移除和显示其中的元素。希望本教程对你有所帮助。

您可能感兴趣的其他 C++ 教程