C++之队列

文章目录

• 1.双端队列
• • 1.1插入元素
  • 1.2删除元素
  • 1.3访问元素
  • 1.4其它特性
• 2.优先队列
• 3.应用：

1.双端队列

1.1插入元素

• 在头部添加元素：

  deq.push_front(x);

• 在末尾添加元素：

  deq.push_back(x);

• 在任意位置插入元素，时间复杂度为O(n)：

  deq.insert(iterator it,int x);

1.2删除元素

• 头部删除元素：

  deq.pop_front();

• 末尾删除元素：

  deq.pop_back();

• 删除任意位置元素，时间复杂度为O(n)：

  deq.erase(iterator it);

• 删除first到last之间的元素：

  deq.erase(iterator first,iterator last);

• 清空元素：

  deq.clear();

1.3访问元素

• 访问元素 除了头部，末尾时间复杂度为O(n)：

  deq[i];deq.at(i);

• 访问头部元素：

  deq.front();

• 访问尾部元素：

  deq.back();

1.4其它特性

• 计算队列大小：

  deq.size();

• 判断对列是否为空：

  deq.empty();

• 翻转队列：

  reverse(deq.begin(),deq.end());

• 对列进行排序：

  sort(deq.begin(),deq.end());

2.优先队列

• 定义：在优先队列中，元素赋予优先级，具有优先级最高先出的特征。

  例如：

  priority_queue<type,container,function>

  。其中type:数据类型；container:实现优先队列的底层容器，例如vector,deque，但不能用list; function:元素之间的比较形式。后面两个参数可以省略，一旦省略，默认是大根推
• 常见成员函数：

  bool empty() const;

  、

  int size() const;

  、

  void pop();//删除队列的顶部元素

  、

  int top(); //与对列q.front()不同,这里是q.top();返回队列顶部元素;

  、

  void push();将元素插到队列中并进行排序

• 大顶堆：

  priority_queue<int> q;

  、

  priority_queue<int,vector<int>,less<int>> q;

• 小顶堆：

  priority_queue<int,vector<int>,greater<int>> q;

  //greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
• 用pair类型做优先队列的例子：

priority_queue<pair<int,int>> q;
pair<int,int> a(1,11);
pair<int,int> b(2,22);
pair<int,int> c(2,33);
q.push(a);
q.push(b);
q.push(c);
while(!q.empty()){
    cout<<q.top().first<<" "<<q.top().second<<endl;
    q.pop();
}
           

• 用pair类型做优先队列（自定义first，second的值的大小）的例子

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> P;
struct cmp{
    bool operator()(const P p1, const P p2){  
        	return p1.second > p2.second; //second的小值优先,恰好相反
    }
};
int main()
{
	priority_queue<P, vector<P>, cmp> que;
	que.push(P(10,20));
	que.push(P(15,30));
	que.push(P(20,1));
	P p;
	while(!que.empty()){
	    p=que.top();
	    que.pop();
	    cout<<p.first<<" "<<p.second<<endl;
	}
}
           

• 自定义类型与优先对列的例子：

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int x;
	int y;
	Node(int x,int y){
		this->x=x;
		this->y=y;
	}
};
struct cmp{
	bool operator()(Node a,Node b){
		if(a.x==b.x) return a.y<b.y;
		return a.x<b.x;//这里符号表示恰好相反
	}
};
int main()
{
    priority_queue<Node,vector<Node>,cmp> q;
    Node a(1,11);
    Node b(2,22);
    Node c(2,33);
    q.push(a);
    q.push(b);
    q.push(c);
    while(!q.empty()){
    	cout<<q.top().x<<" "<<q.top().y<<endl;
    	q.pop();
	}
	return 0;
}
           

3.应用：

• 题目：回文序列：这道题没有很明显提示使用双端对列。但是考虑到回文序列是需要头尾一一对应相等，我们需要对头尾的元素进行去除，因此我们想到双端对列。