Keep In Line

//使用一个双端队列保存元素的入队顺序，方便在队首出队元素和在队尾存放元素
//如果是In，直接将元素保存在双端队列的末尾
//如果是out,且出队元素位于队首，直接出队
//    如果出队元素不位于队首，那么使用哈希表标记该元素已经被删除，等到真
//    正扫描到这个元素的时候，再真正将这个元素移除。
//时间复杂度O(n)
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
 
int main(){
    int T;
    cin >> T;
    while (T--){
        int n;
        cin >> n;
        string Opt, Name;
        deque<string> inOrder;
        unordered_map<string, bool> outmap;
        int count = 0;
        for (int i = 0; i < n; i++){
            cin >> Opt >> Name;
            if (Opt == "in"){
                inOrder.push_back(Name);               
            }
            else{
                if (Name == inOrder[0]){
                    inOrder.pop_front();
                }
                else{
                    while (outmap[inOrder[0]]){
                        inOrder.pop_front();
                    }
                    if (Name == inOrder[0])
                        inOrder.pop_front();
                    else{
                        outmap[Name] = true;
                        count++;
                    }
                }                  
            }
        }
        cout << n / 2 - count << endl;
    }
    return 0;
}

#include<queue>
#include<map>
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int main(){
    int T,n,i;
    for(cin>>T;T--;){
        int res=0;
        map<string,int> book;
        queue<string> Q;
        for(cin>>n;n--;){
            string x,y;
            cin>>x>>y;
            if(x=="in") Q.push(y),book[y]=1;
            else{
                while(book[Q.front()]==0) Q.pop();
                string head=Q.front();
                if(y==head) res++,Q.pop();
                else book[y]=0;
            }
        }
        printf("%d\n",res);
    }
}