題目描述：

/*
小云正在參與開發(fā)一個即時聊天工具，他負(fù)責(zé)其中的會話列表部分。
會話列表為顯示為一個從上到下的多行控件，其中每一行表示一個會話，
每一個會話都可以以一個唯一正整數(shù)id表示。
當(dāng)用戶在一個會話中發(fā)送或接收信息時，
如果該會話已經(jīng)在會話列表中，則會從原來的位置移到列表的最上方；
如果沒有在會話列表中，則在會話列表最上方插入該會話。
小云在現(xiàn)在要做的工作是測試，他會先把會話列表清空等待接收信息。
當(dāng)接收完大量來自不同會話的信息后，
就輸出當(dāng)前的會話列表，以檢查其中是否有bug。
輸入描述:
輸入的第一行為一個正整數(shù)T（T<=10），表示測試數(shù)據(jù)組數(shù)。
接下來有T組數(shù)據(jù)。
每組數(shù)據(jù)的第一行為一個正整數(shù)N（1<=N<=200），表示接收到信息的次數(shù)。
第二行為N個正整數(shù)，按時間從先到后的順序表示接收到信息的會話id。
會話id不大于1000000000。
輸出描述:
對于每一組數(shù)據(jù)，輸出一行，按會話列表從上到下的順序，輸出會話id。
相鄰的會話id以一個空格分隔，行末沒有空格。
輸入例子1:
3
5
1 2 3 4 5
6
1 100 1000 1000 100 1
7
1 6 3 3 1 8 1
輸出例子1:
5 4 3 2 1
1 100 1000
1 8 3 6
*/

思路如下：

類似于lru但是limit是無限制而已
list(自己實(shí)現(xiàn)一個雙向鏈表 或者用vector)+hash_map(用stl)

代碼如下：

#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
 
using namespace std;
 
struct Node
{
    int val=-1;
    Node *prev=NULL, *next=NULL;
    Node() {}
    Node(int val)
    {
        this->val=val;
    }
    Node(const Node &node)
    {
        this->val=node.val;
        this->next=node.next;
        this->prev=node.prev;
    }
};
 
struct NodeList{
    Node *head;
    NodeList(){
        this->head=new Node();
    }
    Node* addNode(int id){
        Node *newNode=new Node(id);
        newNode->next=this->head->next;
        this->head->next=newNode;
        if(newNode->next){
            newNode->next->prev=newNode;
        }
        newNode->prev=this->head;
        return newNode;
    }
    void moveToHead(Node *node){
        //移除
        node->prev->next=node->next;
        if(node->next){
            node->next->prev=node->prev;
        }
        //頭插入
        node->next=this->head->next;
        this->head->next=node;
        node->prev=head;
        if(node->next){
            node->next->prev=node;
        }
    }
};
 
int main()
{
    int T;
    scanf("%d", &T);
    for(int t=0; t<T; t++){
        NodeList *nodeList=new NodeList();
        map<int , Node*> nodeMap;
        int N;
        scanf("%d", &N);
        while(N--){
            int id;
            scanf("%d", &id);
            if(nodeMap.find(id)==nodeMap.end()){
                nodeMap[id]=nodeList->addNode(id);
            }
            else{
                nodeList->moveToHead(nodeMap[id]);
            }
        }
        Node *cur=nodeList->head;
        while(cur->next!=NULL){
            if(cur==nodeList->head){
                printf("%d", cur->next->val);
            }
            else{
                printf(" %d", cur->next->val);
            }
            cur=cur->next;
        }
        printf("\n");
    }
    return 0;
}