C++ 代码
加速优化版
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int e[N], r[N], l[N], idx;
//初始化
void init()
{
// 0代表最左边的头指针, 1代表最右边的尾指针
r[0] = 1, l[1] = 0, idx = 2; // idx = 2, 因此第1个插入的数为2
}
//头指针插入
void add_left(int x)
{
e[idx] = x, r[idx] = r[0], l[idx] = 0, l[r[0]] = idx, r[0] = idx++;
}
//尾指针插入
void add_right(int x)
{
e[idx] = x, l[idx] = l[1], r[idx] = 1, r[l[1]] = idx, l[1] = idx++;
}
// 删除第 k 个插入的数
void remove(int k)
{
r[l[k]] = r[k], l[r[k]] = l[k];
}
//在第k个插入的数的右侧插入一个数
void add(int k, int x)
{
e[idx] = x, r[idx] = r[k], l[idx] = k, l[r[k]] = idx, r[k] = idx++;
}
int main()
{
int m;
scanf("%d", &m);
init();
while (m--)
{
int k, x;
string op;
op.resize(2);
scanf("%s", &op[0]);
//cin >> op;
if (strcmp(op.c_str(), "L") == 0)
{
scanf("%d", &x);
add_left(x);
}
else if (strcmp(op.c_str(), "R") == 0)
{
scanf("%d", &x);
add_right(x);
}
else if (strcmp(op.c_str(), "D") == 0)
{
scanf("%d", &k);
remove(k + 1); // k + 1是因为下边从2开始,因此第1个数对应的下标是2
}
else if (strcmp(op.c_str(), "IL") == 0)
{
scanf("%d%d", &k, &x);
add(l[k + 1], x); // k的左侧的右侧相当于k的左侧插入
}
else if (strcmp(op.c_str(), "IR") == 0)
{
scanf("%d%d", &k, &x);
add(k + 1, x);
}
}
// 头指针对应的数字没有存,是空的,我们是从头指针的下一个指针开始存的数,也就是r[0]
for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
return 0;
}