题解 | 插队-Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);
        
        String[] initialQueue = br.readLine().split(" ");
        
        // 存储每个元素的前驱和后继
        Map<String, String> prev = new HashMap<>();
        Map<String, String> next = new HashMap<>();
        
        // 初始化队列关系
        for (int i = 0; i < n; i++) {
            String current = initialQueue[i];
            // 设置前驱
            if (i > 0) {
                prev.put(current, initialQueue[i - 1]);
            } else {
                prev.put(current, null);
            }
            // 设置后继
            if (i < n - 1) {
                next.put(current, initialQueue[i + 1]);
            } else {
                next.put(current, null);
            }
        }
        
        // 处理每一次插队事件
        for (int i = 0; i < m; i++) {
            String[] parts = br.readLine().split(" ");
            String x = parts[0];  // 要插队的人
            String y = parts[1];  // 要插到谁前面
            
            // 步骤1: 把x从当前位置移除
            String px = prev.get(x);  // x的前驱
            String nx = next.get(x);  // x的后继
            
            // 更新前驱的后继
            if (px != null) {
                next.put(px, nx);
            }
            // 更新后继的前驱
            if (nx != null) {
                prev.put(nx, px);
            }
            
            // 步骤2: 把x插入到y前面
            String py = prev.get(y);  // y的前驱
            
            // 设置x的前驱和后继
            prev.put(x, py);
            next.put(x, y);
            
            // 更新y的前驱的后继
            if (py != null) {
                next.put(py, x);
            }
            // 更新y的前驱为x
            prev.put(y, x);
        }
        
        // 找到队列的头节点（前驱为null的节点）
        String head = null;
        for (String person : initialQueue) {
            if (prev.get(person) == null) {
                head = person;
                break;
            }
        }
        
        // 遍历队列，构建结果
        List<String> result = new ArrayList<>();
        String current = head;
        while (current != null) {
            result.add(current);
            current = next.get(current);
        }
        
        // 输出结果
        System.out.println(String.join(" ", result));
    }
}