题解 | #Keep In Line#

不插队的人出队顺序符合队列的先进先出性质

用队列维护正确的出队顺序，每当有人in使将其插入到队尾，

out时如果这个同学在队头，那么他就不是插队的。

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

public class Main {

	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
        int T = in.nextInt();
        while(T-- != 0) {
            int n = in.nextInt();
            HashMap<String, Boolean> map = new HashMap<>();
            Queue<String> queue = new LinkedList<>();
            int cnt = 0;
            for(int i = 0; i < n; ++i) {
                String strs[] = in.buf.readLine().split(" ");
                if(strs[0].equals("in")) {
                    queue.add(strs[1]);
                    map.put(strs[1], false);
                } else {
                    while(!queue.isEmpty() && map.get(queue.peek()))//先删除已经out的同学
                        queue.poll();
                    if(strs[1].equals(queue.peek()))
                        ++cnt;
                    map.put(strs[1], true);
                }
            }
            out.println(cnt);
        }
		out.close();
	}
}

class InputReader {
	BufferedReader buf;
	StringTokenizer tok;

	InputReader() {
		buf = new BufferedReader(new InputStreamReader(System.in));
	}

	boolean hasNext() {
		while (tok == null || !tok.hasMoreElements()) {
			try {
				tok = new StringTokenizer(buf.readLine());
			} catch (Exception e) {
				return false;
			}
		}
		return true;
	}

	String next() {
		if (hasNext())
			return tok.nextToken();
		return null;
	}

	int nextInt() {
		return Integer.parseInt(next());
	}
}