描述
与y总模板不一样的是,有一个头节点,所以remove那里不用特判了,其余重点见注释(有注释的地方都是和y总模板不一样的地方)
C++ 代码
#include <iostream>
using namespace std;
const int N = 100011;
int e[N], ne[N], head, idx;
void init(){
idx = 0;
head = idx++; // 初始时创建一个头节点,idx为0
e[head] = -1111; // 头节点的值随便赋值一个
ne[head] = -1; // head 的下一个指向空
}
void add_to_head(int x){
e[idx] = x;
ne[idx] = ne[head]; // 插入第一个节点时插入头节点后面
ne[head] = idx; //
idx++;
}
void add(int k, int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void remove(int k){
ne[k] = ne[ne[k]];
}
int main(){
init();
int n;
cin >> n;
while(n--){
int x, k;
char op;
cin >> op;
if(op == 'H'){
cin >> x;
add_to_head(x);
}else if(op == 'D'){
cin >> k;
remove(k);
}else{ // op == 'I'
cin >> k >> x;
add(k, x);
}
}
// i != -1 与上面 init() 的 ne[head] = -1 相对应
for(int i = ne[head]; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}