题目描述

使用数组存储

int e[N]; //结点对应值
int ne[N]; //下一个结点坐标
int idx; //坐标
int h; //头结点坐标

C++ 代码

#include <iostream>

using namespace std;

const int N=1e6;

int e[N],ne[N],idx,h;

void init(){
    h=-1;
    idx=0;
}

void insert(int n){
    e[idx]=n;
    ne[idx]=h;
    h=idx;
    idx++;
}

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

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



int main(){
    init();
    int m;
    cin>>m;
    while(m--){
        char op;
        cin>>op;
        if(op=='H'){
            int a;
            cin>>a;
            insert(a);
        }
        else if(op=='D'){
            int k;
            cin>>k;
            if(k==0) h=ne[h];
            else remove(k-1);
        }
        else if(op=='I'){
            int a,b;
            cin>>a>>b;
            add(a-1,b);
        }
    }
    for(int i=h;i!=-1;i=ne[i]){
        cout<<e[i]<<" ";
    }


    return 0;
}