算法基础-数据结构

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

6 4 6 5

void init(){
    idx = 0;
    head = -1;
}
void add_to_head(int x){
    e[idx] = x; 
    ne[idx] = head;
    head = idx ++ ;
}

void remove(int k){
    ne[k] = ne[ne[k]];
    
}

void insert(int x, int k){
    e[idx] = x; 
    ne[idx] = ne[k];
    ne[k] = idx ++ ;
}

#include <iostream>

using namespace std;

const int N = 100010;
int M;
int ne[N], e[N], idx, head;

void init(){
    idx = 0;
    head = -1;
}
void add_to_head(int x){
    e[idx] = x; 
    ne[idx] = head;
    head = idx ++ ;
}

void remove(int k){
    ne[k] = ne[ne[k]];
    
}

void insert(int x, int k){
    e[idx] = x; 
    ne[idx] = ne[k];
    ne[k] = idx ++ ;
}

int main (){
    cin >> M;
    init();
    while(M --)
    {
        int x, k;
        char op[2]; 
        cin >> op;
        if(*op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(*op == 'D')
        {
            cin >> k;
            if(k)
                remove(k - 1);
            else
                head = ne[head]; // 删除头节点
        }
        else 
        {
            cin >> k >> x; 
            insert(x, k - 1);
        }
    }
    
    for(int i = head; i != -1; i = ne[i])  
        cout << e[i] << " ";
    cout << endl; 
    return 0;
}