下载掌阅APP，畅读海量书库
立即打开
deque是一个双端队列，可以在两端进出队，支持数组表示法和随机访问，经常在序列两端操作时应用。使用deque时，需要引入头文件#include<deque>。
双端队列的成员函数如下。
● push_front( x )/push_back( x )： x 从队头或队尾入队。
● pop_front()/pop_back()：从队头或队尾出队。
● front()/back()：返回队头或队尾元素。
● size()：返回队中的元素个数。
● empty()：判断队空，若为空，则返回true。
● clear()：清空双端队列。
题目描述（HDU6375）： 度度熊正在学习双端队列，它对翻转和合并产生了很大的兴趣。初始时有 N 个空的双端队列（编号为1～ N） ，度度熊的 Q 次操作如下。
①1 u w val：在编号为 u 的队列中加入一个权值为val的元素（ w =0表示加在最前面， w =1表示加在最后面）。
②2 u w ：询问编号为 u 的队列中的某个元素并删除它（ w =0表示询问并操作最前面的元素， w =1表示询问并操作最后面的元素）
③3 u v w ：把编号为 v 的队列“接在”编号为 u 的队列的最后面。 w =0表示顺序接（将队列 v 的开头和队列 u 的结尾连在一起，将队列 v 的结尾作为新队列的结尾）， w =1表示逆序接（先将队列 v 翻转，再按顺序接在队列 u 的后面）。而且在该操作完成后，队列 v 被清空。
输入： 有多组数据。对于每一组数据，第1行都包含两个整数 N 和 Q 。接下来有 Q 行，每行3～4个数，意义如上。 N ≤1.5×10 5 ； Q ≤4×10 5 ；1≤ u , v ≤ N ；0≤ w ≤1；1≤val≤10 5 ；所有数据里 Q 的和都不超过5×10 5 。
输出： 对于每组数据的每一个操作②，都输出一行表示答案。如果操作②的队列是空的，则输出−1且不执行删除操作。
提示： 由于读入过大，建议使用读入优化。一个简单的例子如下。
本题描述的就是双端队列，可以使用deque解决。
（1）定义一个deque数组d[]。
（2）判断分别执行3种操作，第2种操作需要输出。
（3）第3种情况，由于deque不支持翻转，因此可以使用反向迭代器控制。
链表支持翻转和拼接，因此也可以采用链表解决，时间复杂度和空间复杂度更小。
（1）定义一个list []。
（2）判断分别执行3种操作，第2种操作需要输出。
（3）第3种情况，list支持翻转，拼接函数splice可以将另一个链表 v 拼接到当前链表的pos位置之前，并自动清空 v ，且时间复杂度为常数。
