queue类和priority_queue类¶

约 1369 个字 297 行代码预计阅读时间 8 分钟

queue类介绍¶

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。
标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

queue类定义¶

C++
template <class T, class Container = deque<T> > class queue;

queue类为类模板，所以在使用时需要带上类型表示一个具体的类，例如数据类型为int类型的queue使用时需要写为queue<int>

queue类构造函数¶

构造函数	函数原型
无参构造函数	`explicit queue (const container_type& ctnr = container_type());`

Note

上面表格中的构造函数均含有自定义空间配置器并带有缺省值，目前只使用默认即可

Note

使用queue类需要包含头文件<queue>

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    //打印队列
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    return 0;
}
输出结果：
1 2 3 4 5

queue类数据操作¶

函数	功能
`empty()`	判断调用对象队列是否为空
`size()`	获取调用对象队列有效数据个数
`front()`	获取调用对象队列对头数据
`back()`	获取调用对象队列队尾数据
`push()`	向调用对象队列尾部插入数据
`pop()`	弹出调用对象队列对头元素
`swap()`	调用对象队列与指定对象队列交换

`empty()`函数¶

使用empty()函数可以判断调用对象队列是否为空

函数	函数原型
`empty()`	`bool empty() const;`

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    cout << q.empty() << endl;

    return 0;
}
输出结果：
0

`size()`函数¶

使用size()函数可以获取调用对象队列有效数据个数

函数	函数原型
`size()`	`size_type size() const;`

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    cout << q.size() << endl;

    return 0;
}
输出结果：
5

`front()`函数¶

使用front()函数可以获取调用对象队列对头元素

函数	函数原型
`front()`	`value_type& front();`
`const value_type& front() const;`

Note

如果队列为空，此时调用front()函数将会断言报错

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    cout << q.front() << endl;
    return 0;
}
输出结果：
1

`back()`函数¶

使用back()函数可以获取调用对象队列队尾数据

函数原型
`value_type& back();`
`const value_type& back() const;`

Note

如果调用对象队列为空，调用back()函数将会断言报错

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    cout << q.back() << endl;
    return 0;
}
输出结果：
5

`push()`函数¶

使用push()函数可以向调用对象队列中插入数据

函数	函数原型
`push()`	`void push (const value_type& val);`

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    //打印队列
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    return 0;
}
输出结果：
1 2 3 4 5

`pop()`函数¶

使用pop()函数可以弹出调用对象队列对头数据

函数	函数原型
`pop()`	`void pop();`

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);

    //打印队列
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    return 0;
}
输出结果：
1 2 3 4 5

`swap()`函数¶

使用swap()函数可以交换调用对象队列和指定对象队列

函数	函数原型
`swap()`	`void swap (queue& x);`

示例代码：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    queue<int> q1;

    q.push(1);
    q.push(1);
    q.push(1);
    q.push(1);
    q.push(1);

    q1.push(2);
    q1.push(2);
    q1.push(2);
    q1.push(2);
    q1.push(2);

    cout << "交换前：" << endl;
    //打印栈
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    //打印栈
    while (!q1.empty())
    {
        cout << q1.front() << " ";
        q1.pop();
    }
    cout << endl;

    // 注意打印已经使栈为空，需要重新插入元素
    q.push(1);
    q.push(1);
    q.push(1);
    q.push(1);
    q.push(1);

    q1.push(2);
    q1.push(2);
    q1.push(2);
    q1.push(2);
    q1.push(2);

    q.swap(q1);

    cout << "交换后：" << endl;

    //打印栈
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    //打印栈
    while (!q1.empty())
    {
        cout << q1.front() << " ";
        q1.pop();
    }
    cout << endl;

    return 0;
}
输出结果：
交换前：
1 1 1 1 1
2 2 2 2 2
交换后：
2 2 2 2 2
1 1 1 1 1

priority_queue类¶

priority_queue类介绍¶

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素默认它所包含的元素中最大的。
priorit_queue类实际上为堆结构，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。
标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

priority_queue类定义¶

C++
template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

priority_queue类为类模板，所以在使用时需要带上类型表示一个具体的类，例如数据类型为int类型的priority_queue使用时需要写为priority_queue<int>

priority_queue类构造函数¶

构造函数	函数原型
无参构造函数	`explicit priority_queue (const Compare& comp = Compare(), const Container& ctnr = Container());`
迭代器区间构造	`template <class InputIterator> priority_queue (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Container& ctnr = Container());`

Note

使用方法与其他类类似，不再赘述

priority_queue类数据操作¶

函数	功能
`empty()`	判断调用对象堆是否为空
`size()`	获取调用对象堆的有效数据个数
`top()`	获取调用对象堆顶的数据
`push()`	向调用对象堆插入数据
`pop()`	弹出堆顶元素
`swap()`	交换调用对象的堆和指定对象的堆

Note

使用方法与其他类类似，不再赘述

基本使用如下：

C++
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    // 默认为大堆——降序
    priority_queue<int> pq;
    // 上面的写法也可以写成
    // priority_queue<int, vector<int>, less<int>> pq;

    pq.push(1);
    pq.push(5);
    pq.push(6);
    pq.push(2);

    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    // 改为小堆时传仿函数——升序
    // 必须写第二个参数，因为缺省参数必须满足从右向左依次使用
    priority_queue<int, vector<int>, greater<int>> pq1;
    pq1.push(1);
    pq1.push(5);
    pq1.push(6);
    pq1.push(2);

    while (!pq1.empty())
    {
        cout << pq1.top() << " ";
        pq1.pop();
    }

    return 0;
}

输出结果：
6 5 2 1
1 2 5 6

在上面的代码中，less和greater的原型和实现如下：

lessgreater

C++
template <class T> struct less;
// 其实现类似于下面的代码
template <class T> struct less {
    bool operator() (const T& x, const T& y) const 
    {
        return x < y;
    }
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

C++
template <class T> struct greater;
// 其实现类似于下面的代码
template <class T> struct greater {
    bool operator() (const T& x, const T& y) const 
    {
        return x > y;
    }
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

对于less和greater来说，只要满足对应的条件就返回真，如果为真，对于优先级队列来说就是插入数据，所以对于大堆来说，使用less<int>代表当前数值如果小于根节点数值就会因为less<int>返回true插入当前节点，同理可得greater

queue类和priority_queue类¶

queue类介绍¶

queue类定义¶

queue类构造函数¶

queue类数据操作¶

empty()函数¶

size()函数¶

front()函数¶

back()函数¶

push()函数¶

pop()函数¶

swap()函数¶

priority_queue类¶

priority_queue类介绍¶

priority_queue类定义¶

priority_queue类构造函数¶

priority_queue类数据操作¶

`empty()`函数¶

`size()`函数¶

`front()`函数¶

`back()`函数¶

`push()`函数¶

`pop()`函数¶

`swap()`函数¶