c++ 双端队列优先队列

双端队列：

双端队列是指一个可以在队首/队尾插入或删除元素的队列 具体地,双端队列支持的操作有 4 个：

• 在队首插入一个元素

• 在队尾插入一个元素

• 在队首删除一个元素

• 在队尾删除一个元素

数组模拟双端队列的方式与普通队列相同

C++ 中使用STL构造一个queue的语句为： deque <T> q

更多用法可以翻阅文档: http://cplusplus.com/reference/deque/deque/?kw= deque

 接下来给大家看一道双端队列的题目：

题目描述

对于一个队列Q,你需要实现以下几个操作

• 0 d x,当d为0时,将x放入队首,当d为1时将x放入队尾

• 1 idx,输出下标为idx的元素(下标从0开始)

• 2 d,当d为0时,删除队首元素,当d为1时,删除队尾元素

输入格式

第一行输入一个正整数n
接下来n行给出n个操作

保证所有指令都合法

输出格式

对于每个1 idx操作输出一行

输入样例

11
0 0 1
0 0 2
0 1 3
1 0
1 1
1 2
2 0
2 1
0 0 4
1 0
1 1

输出样例

2
1
3
4
1

输出规模

对于全部的数据1≤n≤4×10^5,−10^9≤x≤10^9

AC代码：

#include <bits/stdc++.h>
using namespace std;
deque<int>q;
signed main()
{   int n;cin >> n;while(n--){int op;cin >> op;if(!op){int d,x;cin >> d >> x;if(!d){q.push_front(x);}else{q.push_back(x);}}else if(op==1){int idx;cin >> idx;cout<<q[idx]<<endl;}else if(op==2){int d;cin >> d;if(!d){q.pop_front();}else{q.pop_back();}}}return 0;
}

优先队列：

构造一个类型为Node的优先队列：

priority_queue<Node>q

另外注意：

1.优先队列用到结构体时，必须重载运算符，用比较函数是会CE的！

2.优先队列默认是倒序的！所以重载运算符里面的运算符都要反一下！