度度熊学队列

x33g5p2x  于2022-03-14 转载在 其他  
字(1.7k)|赞(0)|评价(0)|浏览(198)

一 问题描述

度度熊正在学习双端队列,它对翻转和合并产生了很大的兴趣,初始时有 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;
            }
        }
    }
}

四 测试

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

相关文章

微信公众号

最新文章

更多