链表、栈、队列

链表、栈、队列

链表

单链表

一、原理

详见 知乎上一篇写的很好的回答

二、代码实现

数组模拟链表(十分关键,涉及到后续存图所用的链式前向星)

题目:acwing826 单链表

实现一个单链表,链表初始为空,支持三种操作:

(1) 向链表头插入一个数;

(2) 删除第k个插入的数后面的数;

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

(1) “H x”,表示向链表头插入一个数x。

(2) “D k”,表示删除第k个插入的数后面的数(当k为0时,表示删除头结点)。

(3) “I k x”,表示在第k个插入的数后面插入一个数x(此操作中k均大于0)。

输出格式

共一行,将整个链表从头到尾输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
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

输出样例:

1
6 4 6 5

代码:

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
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100050;
int head,nxt[N],e[N];
int n,m,cnt;
void init()
{
head=-1;
cnt=0;
}
void add_head(int x)//将x插到链表头结点
{
e[++cnt]=x;
nxt[cnt]=head;
head=cnt;
}
void add(int x,int k)//将x插到k点的后面
{
e[++cnt]=x;
nxt[cnt]=nxt[k];
nxt[k]=cnt;
}
void remove(int k)//删除k位置上的点
{
nxt[k]=nxt[nxt[k]];
}
int main()
{
init();
cin>>m;
char op;
int x,k;
for(int i=1;i<=m;i++)
{
cin>>op;
if(op=='H')
{
cin>>x;
add_head(x);
}
if(op=='D')
{
cin>>k;
if(k==0)head=nxt[head];
else remove(k);
}
if(op=='I')
{
cin>>k>>x;
add(x,k);
}
}
for(int i=head;i!=-1;i=nxt[i])
{
cout<<e[i]<<" ";
}
return 0;
}

这题的指针写法笔者还没有调出来…感觉相当麻烦…同时指针写法中分配空间耗时较长,会TLE…

三、模板

指针写法链表:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node
{
int data;
node *next;
}a[100050];
int n,m;
node *create()//生成一个长度为n的链表
{
node *head,*p,*tail;
head=NULL;
for(int i=1;i<=n;i++)
{
p=(node *)malloc(sizeof(node));
cin>>p->data;
if(head==NULL)
{
head=p;
tail=p;
}
else
{
tail->next=p;
tail=p;
}
}
tail->next=NULL;
return head;
}
int find(node *head,int x)//获得链表中第x个元素
{
node *p;
p=head;
int i=1;
while(p!=NULL and i<x)
{
p=p->next;
i++;
}
return p->data;
}
node *insert(node *head,int a,int x)//将a元素插入链表中的第x个位置之前
{
node *p;
p=(node *)malloc(sizeof(node));
p->next=head;
int i=1;
if(head==NULL)
{
p->next=0;
return head;
}
while(p!=NULL and i<x)
{
p=p->next;
i++;
}
node *t;
t=(node *)malloc(sizeof(node));
t->data=a;
t->next=p->next;
p->next=t;
return head;
}
node *del(node *head,int a)//将链表中的a元素删除
{
node *p,*t;
p=head,t=head;
int i=1;
if(head->data==a)
{
head=head->next;
}
else
{
while(p!=NULL)
{
t=p;
p=p->next;
if(p->data==a)
{
t->next=p->next;
break;
}
}
}
return head;
}
void print(node *head)//打印链表中的所有元素
{
node *p;
p=head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
}
int main()
{
cin>>n;
node *head,*p,*tail;
head=create();
int x,a;
cin>>a>>x;
head=insert(head,a,x);
cin>>x;
head=del(head,x);
print(head);
return 0;
}

四、例题和应用

  1. 约瑟夫问题
  2. 插入排序

双向链表

一、和单向链表的区别

顾名思义,双向链表中,每个结点既能指向它后面的一个结点,也能指向它前面的一个结点。

二、代码实现

实现一个双链表,双链表初始为空,支持5种操作:

(1) 在最左侧插入一个数;

(2) 在最右侧插入一个数;

(3) 将第k个插入的数删除;

(4) 在第k个插入的数左侧插入一个数;

(5) 在第k个插入的数右侧插入一个数

现在要对该链表进行M次操作,进行完所有操作后,从左到右输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令可能为以下几种:

(1) “L x”,表示在链表的最左端插入数x。

(2) “R x”,表示在链表的最右端插入数x。

(3) “D k”,表示将第k个插入的数删除。

(4) “IL k x”,表示在第k个插入的数左侧插入一个数。

(5) “IR k x”,表示在第k个插入的数右侧插入一个数。

输出格式

共一行,将整个链表从左到右输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
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

输出样例:

1
8 7 7 3 2 9

数组模拟

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100020;
int l[N],r[N],e[N];
int cnt=0;
int m;
void init()
{
//0表示左端点,1表示右端点
r[0]=1,l[1]=0;
cnt=1;
}
void add_r(int k,int x)//在第k个点的右边插入值为x的点
{
e[++cnt]=x;
r[cnt]=r[k];
l[cnt]=k;
l[r[k]]=cnt;
r[k]=cnt; //注意一定要先改变r[k]的左指针,再改变r[k]

}
void add_l(int k,int x)//在第k个点的左边插入值为x的点
{
e[++cnt]=x;
l[cnt]=l[k];
r[cnt]=k;
r[l[k]]=cnt;
l[k]=cnt;
}//也可以调用add_r(l[k],x)
void del(int k)//删除第k个点
{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
void add_head(int x)
{
e[++cnt]=x;
l[cnt]=0; //l->0左端点(无意义)
r[cnt]=r[0];//r->原来的左结点
r[0]=cnt;
l[r[cnt]]=cnt;//原来左结点的l-> cnt
}
void add_tail(int x)
{
e[++cnt]=x;
r[cnt]=1; //r->1右端点(无意义)
l[cnt]=l[1];//l->原来的右结点
l[1]=cnt;
r[l[cnt]]=cnt;//原来右结点的 r-> cnt
}
int main()
{
ios::sync_with_stdio(false);
cin>>m;
string op;
int k,x;
init();//因为没有初始化调了好久...引以为戒
for(int i=1;i<=m;i++)
{
cin>>op;
if(op=="L")
{
cin>>x;
add_head(x);//add_r(0,x);
}
else if(op=="R")
{
cin>>x;
add_tail(x);//add_l(1,x);
}
else if (op=="D")
{
cin>>k;
del(k+1);//因为初始化加了两个节点,cnt从2开始,所以第k个数的下标为k+1
}
else if (op=="IL")
{
cin>>k>>x;
add_l(k+1,x);
}
else if(op=="IR")
{
cin>>k>>x;
add_r(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i])
{
cout<<e[i]<<" ";
}
return 0;
}

一、原理

先进后出

二、代码实现

实现一个栈,栈初始为空,支持四种操作:

(1) “push x” – 向栈顶插入一个数x;

(2) “pop” – 从栈顶弹出一个数;

(3) “empty” – 判断栈是否为空;

(4) “query” – 查询栈顶元素。

现在要对栈进行M个操作,其中的每个操作3和操作4都要输出相应的结果。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。

输出格式

对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。

其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示栈顶元素的值。

数据范围

1≤M≤100000
1≤x≤$$10^9$$
所有操作保证合法。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例:

1
2
3
4
5
5
5
YES
4
NO

栈 模板

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
#include<iostream>
#include<stack>
using namespace std;
const int N=100010;
int s[N],top=0;
stack<int> st;
int main()
{
int m;
cin>>m;
while(m--)
{
string op;
int x;
cin>>op;
if(op=="push")
{
cin>>x;
s[++top]=x;//st.push(x); 入栈
}
else if(op=="pop")top--;//st.pop(); 出栈
else if(op=="empty")
{
if(top) printf("NO\n");//if(!st.empty()); 判断栈是否为空
else printf("YES\n");
}
else
{
cout<<s[top]<<endl;//st.top(); 取出栈顶元素
}
}
return 0;
}

队列

一、原理

先进先出

二、代码实现

实现一个队列,队列初始为空,支持四种操作:

(1) “push x” – 向队尾插入一个数x;

(2) “pop” – 从队头弹出一个数;

(3) “empty” – 判断队列是否为空;

(4) “query” – 查询队头元素。

现在要对队列进行M个操作,其中的每个操作3和操作4都要输出相应的结果。

输入格式

第一行包含整数M,表示操作次数。

接下来M行,每行包含一个操作命令,操作命令为”push x”,”pop”,”empty”,”query”中的一种。

输出格式

对于每个”empty”和”query”操作都要输出一个查询结果,每个结果占一行。

其中,”empty”操作的查询结果为“YES”或“NO”,”query”操作的查询结果为一个整数,表示队头元素的值。

数据范围

1≤M≤100000
1≤x≤$$10^9$$
所有操作保证合法。

输入样例:

1
2
3
4
5
6
7
8
9
10
11
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例:

1
2
3
4
NO
6
YES
4

队列模板

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
#include<iostream>
using namespace std;
const int N=100010;
int q[N],hh=1,tt=0;
int m;
int main()
{
ios::sync_with_stdio(false);
cin>>m;
while(m--)
{
string op;
int x;
cin>>op;
if(op=="push")
{
cin>>x;
q[++tt]=x;//q.push(x); 入队
}
else if(op=="pop")hh++;//q.pop(); 出队
else if(op=="empty")
{
cout<<(hh>tt?"YES":"NO")<<endl;
//!q.empty(); 判断队列是否为空
}
else cout<<q[hh]<<endl;//q.front(); 取出队头元素
}
return 0;
}
//类比双向链表,同样存在双端队列,即既可以从队头出队,也可以从队尾出队
//STL中的 deque即为双端队列

单调栈

一、使用背景

给定一个序列,求这个序列中每一个数的某一侧(左、右)离它最近的且满足某种性质的数在哪。

二、例题

acwing 830 单调栈

给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。

输入格式

第一行包含整数N,表示数列长度。

第二行包含N个整数,表示整数数列。

输出格式

共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。

数据范围

1≤N≤$$10^5$$
1≤数列中元素≤$$10^9$$

输入样例:

1
2
5
3 4 2 7 5

输出样例:

1
-1 3 -1 2 2

解析:

  1. 考虑最最暴力的做法,对每一个数都枚举它左边的所有数,直到找到符合条件的为止,复杂度O($$n^2$$)

  2. 简单优化:从它的上一个数开始找,找到符合条件的就停,还是O($$n^2$$)

  3. 基于方法2的想法:对于当前的数,与之前的数比较,如果它比之前的数都要小(并且已经在之前的数后面出现),说明它更有潜力成为“第一个”符合条件(比当前数小)的数,那么就可以淘汰掉前面那些数了(因为他们永远不可能成为后面的数的答案),此时与栈这种数据结构结合就可以维护一个单调的序列。

    举例说明:设存在a[i](i>5>3), a[3]>a[5] 且3<5,那么a[3]一定不会成为a[i]的答案,因为a[5]一定更优

代码:

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
#include<iostream>
#include<cstdio>
#include<stack>
#include<climits>
using namespace std;
const int N=100050;
int n;
int a[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
stack<int> s;
s.push(INT_MAX);
for(int i=1;i<=n;i++)
{
while(!s.empty() and a[i]<=s.top())
{
s.pop();
}//把那些已经没有潜力成为答案的数全部踢出去
if(s.empty())
{
cout<<"-1 ";
s.push(a[i]);
}//如果全部都不能成为答案就是无解
else
{
cout<<s.top()<<" ";
s.push(a[i]);
}
}
return 0;
}

单调队列

一、使用背景

滑动窗口中的最值

**“如果一个选手比你小还比你强,你就可以退役了。” ** ——单调队列的原理

二、例题

luogu P1886 滑动窗口

给定一个大小为n≤$$10^6$$的数组。

有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为[1 3 -1 -3 5 3 6 7],k为3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n和k,分别代表数组长度和滑动窗口的长度。

第二行有n个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

1
2
8 3
1 3 -1 -3 5 3 6 7

输出样例:

1
2
-1 -3 -3 -3 3 3
3 3 5 5 6 7

解析

  1. 先考虑暴力做法,对每个窗口都枚举,时间复杂度O(nk)

  2. 与单调栈例题类似的想法,如果后面出现的数比前面出现的更优,那么前面的数就可以直接踢出去了。那么我们每次加入队列后面的一定是次优值,在队头的最优值被踢掉之后有潜力成为新的最优值,即整个队列一定是单调的,并且对于每一个窗口,队头元素都是我们要找的最优值!

    我们把每一次求极值都变成直接访问队头,O(k)的操作就变成O(1),时间复杂度就降低了。

    举例说明:我们现在要找最小值,在 3 -1 -3 这个k=3的窗口中,只要 -3 存在,那么3和-1一定是没有用且永无出头之日(因为-3在他们的后面,会在更晚的时间被弹出窗口),他们失去了成为最小值的潜力,直接踢出去即可。

    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
    52
    53
    54
    55
    56
    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    const int N=2000050;
    int n,k;
    int a[N];
    deque<int> maxq,minq,q;
    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {

    while(minq.front()<=i-k and !minq.empty())
    {
    minq.pop_front();//从队头弹出,丢掉所有下标不符合条件的数
    }//看看下标在不在这个窗口的范围内
    while(!minq.empty() and a[minq.back()]>a[i])
    {
    minq.pop_back();//从队尾弹出维护次优值
    }//维护一个单调增的最小值队列
    minq.push_back(i);
    if(i>=k)
    {
    cout<<a[minq.front()]<<" ";
    }
    }
    cout<<endl;
    //做题时遇到的问题:如何在窗口移动后把早出现的值踢出去?
    //法1.将下标加入队列而不是将值加入队列!
    //法2.用结构体两个一起维护
    for(int i=1;i<=n;i++)
    {
    while(maxq.front()<=i-k and !maxq.empty())
    {
    maxq.pop_front();
    }
    while(!maxq.empty() and a[maxq.back()]<a[i])
    {
    maxq.pop_back();
    }//维护一个单调减的最大值队列
    maxq.push_back(i);
    if(i>=k)
    {
    cout<<a[maxq.front()]<<" ";
    }
    }
    return 0;
    }