链表、栈、队列

Created2021-02-22Updated2021-02-22

链表、栈、队列

链表

单链表

一、原理

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

二、代码实现

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

题目：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;
    }