语法总结——队列

队列

优先队列

头文件

#include<queue>

特点

• 在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征
• 优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

定义

/*
Type： 数据类型
Container: 容器类型（必须是用数组实现的容器，vector,deque等，不能用List）
Functional: 比较的方式
*/
priority_queue<Type, Container, Functional>

• 对于基本类型，默认使用大顶堆

• 示例:

  priority_queue<int> a;
  priority_queue <int,vector<int>,greater<int> > q;	//主动声明 小顶堆
  priority_queue<string> b
  priority_queue<pair<int, int> > a	//pair先比较第一个

基本操作函数

函数	作用
top	访问队头元素
empty	队列是否为空
size	返回队列内元素个数
push	插入元素到队尾 (并排序)
pop	弹出队头元素
swap	交换内容

进阶操作

• 自定义类型

  //方法1
  struct tmp1 //运算符重载<
  {
      int x;
      tmp1(int a) {x = a;}
      bool operator<(const tmp1& a) const		//注意这里重载 <
      {
          return x < a.x; //大顶堆
      }
  };
  
  //方法2
  struct tmp2 //重写仿函数
  {
      bool operator() (tmp1 a, tmp1 b)		//这里重载()
      {
          return a.x < b.x; //大顶堆
      }
  };
  
  int main()
  {
      tmp1 a(1);
      tmp1 b(2);
      tmp1 c(3);
      priority_queue<tmp1> d;
      d.push(b);
      d.push(c);
      d.push(a);
      while (!d.empty())
      {
          cout << d.top().x << '\n';
          d.pop();
      }
      cout << endl;
  
      priority_queue<tmp1, vector<tmp1>, tmp2> f;
      f.push(b);
      f.push(c);
      f.push(a);
      while (!f.empty())
      {
          cout << f.top().x << '\n';
          f.pop();
      }
  }

扩展阅读

• c++优先队列(priority_queue)用法详解