当前位置 博文首页 > 广大菜鸟的博客：算法学习(5) 数据结构：用数组实现单链表/栈/队
https://www.acwing.com/problem/content/828/
输入样例：
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
#include<iostream>
using namespace std;
const int N = 100010;
// head 头结点下标，e[i]表示结点i的值
// ne[i]表示下一个结点的下标,idx表示当前已经用到了哪个点
int head, e[N], ne[N],idx=0;
//初始化
void init() {
head = -1;
idx = 0;
}
// 插入头节点 “H x”，表示向链表头插入一个数x。
void add_to_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 插入指定结点后 “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。
void insert(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 删除k结点后一个点， “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。
void remove(int k) {
ne[k] = ne[ne[k]];
}
int main() {
init();
int m;
cin >> m;
while (m--) {
char a;
int k, x;
cin >> a;
if (a == 'H') {
cin >> x;
add_to_head(x);
}
else if (a == 'I') {
cin >> k >> x;
insert(k-1, x);
}
else {
cin >> x;
if (!x)
head = ne[head];
remove(x-1);
}
}
for (int i = head; i != -1; i = ne[i])
cout << e[i] << " ";
}
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2 9
#include<iostream>
using namespace std;
const int N = 100010;
// head 头结点下标，e[i]表示结点i的值
// ne[i]表示下一个结点的下标,idx表示当前已经用到了哪个点
int head, e[N], l[N],r[N],idx=0;
// 初始化
void init() {
// 0 表示左端点，1表示右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 第k个点右边插入一个点
void IR(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 第k个点左边插入一个点
void IL(int k, int x) {
e[idx] = x;
l[idx] = l[k];
r[idx] = k;
r[l[k]] = idx;
l[k] = idx;
idx++;
}
// 删除第k个结点
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
// “L x”，表示在链表的最左端插入数x。
void L(int x) {
e[idx] = x;
l[idx] = 0;
r[idx] = r[0];
r[0] = idx;
l[r[idx]] = idx;
idx++;
}
//“R x”，表示在链表的最右端插入数x。
void R(int x) {
e[idx] = x;
r[idx] = 1;
l[idx] = l[1];
r[l[idx]] = idx;
l[1] = idx;
idx++;
}
int main() {
ios::sync_with_stdio(false);
init();
int m; cin >> m;
string opt;
int k, x;
while (m--) {
cin >> opt;
if(opt== "L"){
cin >> x;
L(x);
}
else if (opt == "R") {
cin >> x;
R(x);
}
else if (opt == "D") {
cin >> k;
remove(k+1);
}
else if (opt == "IL") {
cin >> k >> x;
IL(k+1, x);
}
else if (opt == "IR") {
cin >> k >> x;
IR(k+1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) {
cout << e[i] << " ";
}
}
/*
(1) “L x”，表示在链表的最左端插入数x。
(2) “R x”，表示在链表的最右端插入数x。
(3) “D k”，表示将第k个插入的数删除。
(4) “IL k x”，表示在第k个插入的数左侧插入一个数。
(5) “IR k x”，表示在第k个插入的数右侧插入一个数。
输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2 9
*/
#include<iostream>
using namespace std;
const int N = 10010;
int stk[N], stt=0;
//========= 栈 ==================
// 插入
void push(int x) {
stk[++stt] = x;
}
// 弹出
void pop() {
stt--;
}
//判断是否为空
bool isempty() {
return stt > 0;
}
//栈顶
int top() {
return stk[stt];
}
#include<iostream>
using namespace std;
const int N = 10010;
int q[N], hh, tt = -1;
// 插入
void push(int x) {
q[++tt] =
