一 问题描述

度度熊正在学习双端队列，它对翻转和合并产生了很大的兴趣，初始时有 N 个空的双端队列（编号从1到N），度度熊的 3 种操作如下。

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 个数。

输出：对于每组数据的每一个操作 2，都输出一行表示答案。如果操作 2 的队列是空的，则输出 -1，且不执行删除操作。

输入样例
2 10

1 1 1 23

1 1 0 233

2 1 1

1 2 1 2333

1 2 1 23333

3 1 2 1

2 2 0

2 1 1

2 1 0

2 1 1

输出样例

23

-1

2333

233

23333

二 算法设计

本题描述的就是双端队列，可以使用 LinkedList 解决。

1 定义一个 LinkedList 的列表。

2 判断分别执行 3 种操作，第 2 种操作需要输出。

3 第 3 种情况，由于 LinkedList  不支持翻转，可以通过集合工具类辅助解决。

三 实现

package LinkedListDemo;

import java.util.*;

public class DuDuXiong {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 表示有多少个队列
        int n = scanner.nextInt();
        // 表示有多少组数据
        int m = scanner.nextInt();
        // 构造队列
        List<LinkedList> dequeList = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            dequeList.add(new LinkedList());
        }
        // 表示哪种类型的操作，只能是 1，2 ，3
        int k;
        // 表示队列的编号
        int u;
        // 表示队列的编号
        int v;
        // 当 w=0,表示在队头操作，当 w=1，表示在队尾操作
        int w;
        // 表示权值
        int val;
        while (m-- > 0) {
            k = scanner.nextInt();
            switch (k) {
                case 1:
                    u = scanner.nextInt();
                    w = scanner.nextInt();
                    val = scanner.nextInt();
                    if (w == 0) {
                        dequeList.get(u).offerFirst(val);
                    } else {
                        dequeList.get(u).offerLast(val);
                    }
                    break;
                case 2:
                    u = scanner.nextInt();
                    w = scanner.nextInt();
                    if (dequeList.get(u).isEmpty()) {
                        System.out.println("-1");
                    } else {
                        if (w == 0) {
                            System.out.println(dequeList.get(u).pollFirst());
                        } else {
                            System.out.println(dequeList.get(u).pollLast());
                        }
                    }
                    break;
                case 3:
                    u = scanner.nextInt();
                    v = scanner.nextInt();
                    w = scanner.nextInt();
                    if (w == 0) {
                        dequeList.get(u).addAll(dequeList.get(u).size(), dequeList.get(v));
                    } else {
                        Collections.reverse(dequeList.get(v));
                        dequeList.get(u).addAll(dequeList.get(u).size(), dequeList.get(v));
                        dequeList.get(v).clear();
                    }
                    break;
            }
        }
    }
}

四 测试

绿色表示输入，白色表示输出。