家庭作业

必做

• 队列练习2
• 堆排序
• 第k大的数

提高

• 世界杯
• Cow Line S

双端队列

概述：deque（双端队列）是由一段一段的定量连续空间构成，可以向两端发展，因此不论在尾部或头部安插元素都十分迅速。 在中间部分安插元素则比较费时，因为必须移动其它元素。

#include <deque> // deque属于std命名域的，因此需要通过命名限定，例如using std::deque;
#include <iostream>

using namespace std;

itn main(){
    deque<int> qu; // 定义一个int类型的双端队列que
    return 0;
}

常用操作函数

• 获取容器大小：que.size();
• 容器判空（返回值为0时表示非空，1表示空）：que.empty();
• 队首添加元素：que.push_front(元素);
• 队尾添加元素：que.push_back(元素);
• 删除队首元素：que.pop_front();
• 删除队尾元素：que.pop_back();
• 清空所有元素：que.clear();
• 下标访问（并不会检查是否越界）：que[1];
• 访问第一个元素：que.front();
• 访问最后一个元素：que.back();

优先队列

优先队列优先级修改

//普通优先队列
priority_queue<int> q; //定义一个优先队列，默认为大顶堆
priority_queue<int, vector<int>, less<int> > a; //大顶堆 大的在队首
priority_queue<int, vector<int>, greater<int> > b; //小顶堆 小的在队首
//优先队列参数：
//一：队列中储存的数据类型
//二：堆的数据结构，默认为vecotr<int>，尽量不去做修改
//三：队列中数据的优先级

//结构体优先队列
struct Node{
    int x, y;
};
//重载运算符
bool operator<(Node a, Node b){//返回true时，说明a的优先级低于b
    //x值较大的Node优先级低（x小的Node排在队前）
    //x相等时，y大的优先级低（y小的Node排在队前）
    if( a.x== b.x ) return a.y> b.y;
    return a.x> b.x;
}
priority_queue<Node> que; //定义一个储存Node结构体变量的队列，并且在优先级规则上按照上面重载的运算符规则进行，如果未重载运算符，会直接报错