C++提供队列是一种容器适配器，符合数据结构中队列的特征，是一种FIFO的数据结构

  • back() 返回队尾数据的一个引用
  • empty() 如果队列为空，返回true，否则返回false
  • front() 返回队首元素的引用
  • pop() 将队首元素出队
  • push() 将一个元素入队
  • size() 返回队列中元素的个数

队列的衍生容器

deque 双向队列

  • deque() 构造器
    能通过以下四种方式创建：
    • 无参：创建一个空的双向队列
    • size：创建一个大小为size的双向队列
    • num and val：放置num个val的拷贝到队列中
    • from deque：从from创建一个内容一样的双向队列
  • assign(num,val)：给双向队列设置num个val的值
  • at(pos)：返回指向双向队列中位置pos上的元素的引用
  • pop_back()：删除双向队列尾部的元素
  • pop_front()：删除双向队列头部的元素
  • push_back()：向队列尾部添加元素
  • push_front()：向队首添加元素

priority queue 优先队列

在优先队列中，存储的元素被赋予了优先级别。当访问元素的时候，具有最高优先级别的元素会最先被删除。

  • priority_queue()：构造器
    使用基本的数据类型的时候，只需要传入数据类型；默认是大根堆
    使用自定义的数据类型的时候，需要指定三个参数
    priority_queue<Type,Container,Functional>

    1. // 升序队列，小根堆
    2. priority_queue<int,vector<int>,greater<int>> q;
    3. // 降序队列，大根堆
    4. priority_queue<int,vector<int>,less<int>> q;

    使用自定义数据类型：
    按照Person类的number较大值设置优先级，（**number**大的先出）

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. class Person{
    4. public:
    5.   int number;
    6.   Person(){
    8.   }
    9.   Person(int number){
    10.       this->number = number;
    11.   }
    12.   bool operator<(const Person& p) const{
    13.       return this->number < p.number;
    14.   }
    15. };
    16. class Person_Comparable{
    17. public:
    18.   bool operator()(Person p1,Person p2){
    19.       return p1.number < p2.number;
    20.   }
    21. };
    22. int main(){
    23.   priority_queue<Person,vector<Person>,Person_Comparable> q;
    24.   Person p1(1);
    25.   Person p2(2);
    26.   Person p3(3);
    27.   q.push(p1);
    28.   q.push(p2);
    29.   q.push(p3);
    30.   while(!q.empty()){
    31.       cout << q.top().number << endl;
    32.       q.pop();
    33.   }
    34.   system("pause");
    35.   return 0;
    36. }

  • top()返回优先队列中有最高优先级的元素