数据结构——队列

FIFO，先进先出

数据结构——队列

语法：template<class T, class Container = deque<T> > class queue

特性：FIFO，先进先出，队尾插入、队头删除

引用：include<queue>

函数

empty	如果队列为空，则该函数返回true，否则返回false
size	返回队列中元素的个数
push	在末尾插入一个新元素，返回值为void
pop	删除第一个元素，返回值为void
front	返回第一个元素
back	返回最后一个元素

leetcode题库

题目	题解
225.用队列实现栈	双队列，push时不断交换，让栈顶始终在队头
232.用栈实现队列	双栈，push时不断倒换，让队头始终在栈顶
341.扁平化嵌套列表迭代器	深度优先遍历 + 队列的应用 + 现学接口如何使用
387.第一个唯一字符	两次遍历字符串，用map或者int数组保存字符出现次数，简单题
239.滑动窗口最大值	双向队列deque，保存数组指针（而非数组值），队头到队尾单调递减。空间换时间，困难题 拓展：滑动窗口平均值

双向队列，deque

引用：include<deque>

函数

push_back	插入队尾
push_front	插入队头
pop_back	从队尾删除
pop_front	从队头删除
front	返回队头元素
back	返回队尾元素
insert	insert (iterator position, const value_type& val)，指定位置插入值 void insert (iterator position, size_type n, const value_type& val)，指定位置插入值，重复插入n个 void insert (iterator position, InputIterator first, InputIterator last)，指定位置插入另外一个容器的值列表
erase	两种参数， erase (iterator position); erase (iterator first, iterator last);
size

优先队列，priority_queue

引用：include<queue>

特性：优先队列类似于堆，其中优先级最高的元素会被最先pop()弹出，或者用top()访问优先级最高的元素。

语法：priority_queue<Type, Container, Functional>

• 其中type为数据类型，Container为容器类型，Functional是比较方式

• 示例：

  //升序队列
  priority_queue <int,vector<int>,greater<int> > q;
  //降序队列
  priority_queue <int,vector<int>,less<int> >q;
  //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
  
  //对于基础类型 默认是大顶堆
  priority_queue<int> a; 
  //等同于 priority_queue<int, vector<int>, less<int> > a;
  
  //结构体自定义排序方法
  struct tmp1 //运算符重载<
  {
      int x;
      tmp1(int a) {x = a;}
      bool operator<(const tmp1& a) const
      {
          return x < a.x; //大顶堆
      }
  };
  priority_queue<tmp1> pq;
  
  //在结构体外重载结构体指针比较方法。优先队列的元素为结构体指针，而不是结构体（特殊），最小顶堆
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
  struct cmp{
          bool operator()(ListNode* a,ListNode* b){
              return a->val>b->val;
          }
      };
  priority_queue<ListNode*, vector<ListNode*>, cmp> Q;

函数

push()	它将新元素插入优先队列。
pop()	它将优先级最高的元素从队列中删除。
top()	此函数用于寻址优先队列的最顶层元素。
swap()	它将优先队列的元素与具有相同类型和大小的另一个队列交换。
size()	返回优先队列的大小。
empty()	它验证队列是否为空。基于验证，它返回队列的状态。
emplace()	它在优先队列的顶部插入一个新元素。