https://www.acwing.com/problem/content/828/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstddef>
#include <vector>
using namespace std;
#define N 100010
// head 表示头指针，初始值为 NULL(尾节点的序号)，注意：头节点（空节点）没有序号，尾节点没有指针
// e[], ne[] 数组分别存储每个节点的数据域和指针域（指向直接后继的序号）
// idx 记录现在用的是第几个节点（idx = 1, 2, 3, ...）
int list[N];
int head, e[N], ne[N], idx;
void init()
{
head = NULL;
idx = 0;
}
void add_to_head(int x)
{
e[++ idx] = x;
ne[idx] = head;
head = idx;
}
void add(int k, int x)
{
e[++ idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
init();
while(m --)
{
char ch[2];
int k, c;
scanf("%s", ch);
if(ch[0] == 'H')
{
scanf("%d", &c);
add_to_head(c);
}
else if(ch[0] == 'D')
{
scanf("%d", &k);
if(!k) head = ne[head];
// 如果k为0 代表删除首元节点（第一个有数据域的节点）
remove(k);
}
else
{
scanf("%d%d", &k, &c);
add(k, c);
}
}
printf("%d", e[head]);
for (int i = ne[head]; i != NULL; i = ne[i])
{
printf(" %d", e[i]);
}
puts("");
return 0;
}