1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

const int N = 100010
int e[N], ne[N], head, idx;
void init(){
  head = -1;
  idx = 0;
}
void addToHead(int x) {
  e[idx] = x;
  ne[idx] = head;
  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]];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

//构建静态链表的大小----数组模拟链表就是构建了一个静态链表
const int N = 100010;
//head始终表示头结点的下标, idx 表示的是当前操作节点的下标
int e[N], ne[N], head, idx;

//初始化链表
void init(){
    //head=-1说明当前为空集
    head = -1;
    //idx=0表示要操作的节点的下标为 0
    idx = 0;
}

//向链表头插入一个数；
void insertHead(int x) {
    /*
    1. 把这个数存到节点里
    2. 让这个节点指向当前的头结点
    3. 让 head 指向当前节点
    4. idx++, 让他指向下一个要操作的节点
    */
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 删除下标为 k 的后一个节点
void remove(int k) {
    /*
    1. 找到下标为 k 的节点的下一个节点的下一个节点
    2. 更新下标为 k 的节点的下一个节点
    */
    //ne[k]表示下一个节点的位置, 由于ne[i]表示节点i的下一个节点位置, 所以 ne[ne[k]]表示下标为k的节点的下一个节点的下一个节点
    ne[k] = ne[ne[k]];
}

//在下标为k的节点后插入一个节点
void insert(int k, int x) {
    /*
    1. 把这个数存到节点里
    2. 让当前操作节点指向下标 k 的节点的下一个节点
    3. 让下标为k 的节点指向当前节点
    4. 更新 idx 到下一个要操作的节点, idx++
    */
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}
 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

const int N = 100010;
int e[N], l[N], r[N], idx;
void init(){
 	r[0] = 1;
  l[1] = 0; 
  idx = 2;
}

void add(int k, int x){
	e[idx] = x;
	r[idx] = r[k];
  l[idx] = k;
  l[r[k]] = idx;
  r[k] = idx;
  idx++;
}

void remove(int k) {
  r[l[k]] = r[k];
  l[r[k]] = l[k];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//声明静态链表长度, 一般由输入的数据量决定
const int N = 100010;
//e[i]表示下标为i的节点的值, l[i]表示下标为i的节点的左指针(左节点下标), r[i]表示下标为i的节点的右指针(右节点下标), idx 表示正在处理的节点的下标
int e[N], l[N], r[N], idx;
//双链表使用两个节点来初始化, 分别是 head 节点和 tail 节点, 互相指向表示空链表, 同时这两个节点可以定义出链表的边界
void init(){
    //让 head 节点指向 tail 节点
	r[0] = 1;
    //让 tail 节点指向 head 节点
 	l[1] = 0; 
    //由于 0 1 位置被占用了, 所以 idx 从 2 开始
	idx = 2;
}

//add操作表示在 idx 为 k 的节点右边插入节点
void add(int k, int x){
    //存储节点值
	e[idx] = x;
    //让当前操作节点右指针指向下标为k的节点的右节点
	r[idx] = r[k];
    //让当前操作节点左指针指向下标为k的节点
    l[idx] = k;
    //让下标为k的节点的右节点的左指针指向当前节点
    l[r[k]] = idx;
    //让下标为k的节点的右指针指向当前节点 --- 这一步不能和上一步调换
    r[k] = idx;
    //操作下一个节点
    idx++;
}
//注意: 这里的 k 指的值要执行的节点下标而不是说删除第 k 个节点的右一个节点 --- 这是和单链表不同的地方
void remove(int k) {
    //让待删除节点的 左节点的右指针 指向 待删除节点的右节点
    r[l[k]] = r[k];
    //让待删除节点的 右节点的左指针 指向 待删除节点的左节点
    l[r[k]] = l[k];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

const int N = 1000010;
//tt 表示栈顶指针, 这里我们以 0 表示栈中没有元素
int stk[N], tt;
//向栈顶插入元素
stk[ ++ tt ] = x;
//弹出元素
tt--;
//获取栈顶元素
stk[tt];
//判空
if(tt > 0) not empty

1
2

序列: 	3	4	2	7	5
ans: 	 -1	 3	 -1	 2	 2

1
2
3
4
5
6
7
8
9

for(int i = 0; i< n; i++){
	for(int j = i - 1; j >= 0; j--){
    	if(arr[i] > arr[j]) {
        	cout << arr[j] << endl;
            break;
        }
    }
    cout << "-1" << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const int N = 100010;
int a[N];
int stk[N], tt = 0;
void pop(){
	tt--;
}
void push(int x) {
	stk[++ tt] = x;
}
bool empty() {
	return !(tt > 0);
}
int query() {
	return stk[tt];
}

void find(int n){
	for(int i = 0; i < n; i++) {
    	while(!empty() && query() >= a[i]) {
        	pop();
        }
        if(empty()) {
    		cout << "-1" << " ";
        }else {
        	cout << query() << " ";
        }
        push(a[i]);
    }
}