数据结构【上】_链表 给定n个数字,从左到右编号为1~n,接下来进行m次操作,请输出操作后的序列。 操

单链表

单链表常用于存储树和图。

实现一个单链表，链表初始为空，支持三种操作
1.向链表头插入一个数;
2.删除第k个插入的数后面的数
3.在第k个插入的数后插入一个数
现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了 n个数，则按照插入的时间顺序，这n个数依次为:第 1个插入的数，第 2个插入的数，..第n 个插入的数
输入格式
第一行包含整数M，表示操作次数
接下来 M行，每行包含一个操作命令，操作命令可能为以下几种
1. H x, 表示向链表插入一个数 t。
2. D k,  表示删除第k个插入的数后面的数(当k为0时，表示删除头结点)。
3. I k x，表示在第 k个插入的数后面插入一个数 x (此操作中均大于0)
输出格式
共一行，将整个链表从头到尾输出
数据范围
1 ≤ M ≤ 100000
所有操作均保证合法。
输入样例：

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 <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//elem[] 存值， ne[] 存next地址, h头指针, idx当前
int elem[N], ne[N], h = -1, idx = 1;
//注意:如果idx = 0， 后面的k需要-1，题目中要增删的是第k个数后面的数
//头插
void push_head(int x)
{
    elem[idx] = x;//赋值
    ne[idx] = h;//指向下一个
    h = idx ++;
}
//插入
void push(int k, int x)
{
    elem[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}
//删除
void pop(int k)
{
    if(k == 0){
        h = ne[h];
    }else{
        ne[k] = ne[ne[k]];
    }
}
int main()
{
    int m;
    cin >> m;
    while(m--){
        char op;
        int k, x;
        cin >> op;
        if(op == 'H'){
            cin >> x;
            push_head(x);
        }else if(op == 'I'){
            cin >> k >> x;
            push(k, x);
        }else if(op == 'D'){
            cin >> k;
            pop(k);
        }
    }
    for(int i = h; i != -1; i = ne[i]){
        cout << elem[i] << " ";
    }
    return 0;
}

双链表

实现-个双链表，双链表初始为空，支持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
所有操作保证合法。
输入样例：

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

思路：首先初始化，0表示左边，1表示右边。可以看成是两条单链表，一条都是指向左，另一条都是指向右。

代码

#include <bits/stdc++.h>
using namespace std;
const int  N = 1e5 + 10;
int e[N], l[N], r[N], idx;
void init()
{
    l[1] = 0;
    r[0] = 1;// 0 表示左边， 1表示右边
    idx = 2;
}
//在k后添加 x
void add(int k, int x){
    e[idx] = x;//赋值
    l[r[k]] = idx;//k的右节点向左指向 idx
    l[idx] = k;// idx的向左指向 k
    r[idx] = r[k];// idx 向右指向 k的右节点
    r[k] = idx ++;//k向右指向 idx
}
// 删除第k个点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
int main()
{
    int m;
    cin >> m;
    init();
    while(m --){
        string s;
        cin >> s;
        int k, x;
        if(s == "L"){
            cin >> x;
            add(0, x);// 最左边是0
        }else if(s == "R"){
            cin >> x;
            add(l[1], x);//最右边是1，1的左节点
        }else if(s == "D"){
            cin >> k;
            remove(k+1);// idx从2开始，所以操作的k要+1
        }else if(s == "IL"){
            cin >> k >> x;
            add(l[k+1], x);
        }else if(s == "IR"){
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for(int i = r[0]; i != 1; i = r[i]){
    	cout << e[i] << " ";
	}
	cout << "\n";
    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
所有操作保证合法
输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

 思路：栈是一个先进后出的数据结构，用数组模拟的时候，可以直接用一个指针idx，添加元素时指针后移，删除元素时指针前移。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int st[N], idx = 0;
int main()
{
    int m;
    cin >> m;
    while(m --){
        string s;
        cin >> s;
        int x;
        if(s == "push"){
            cin >> x;
            st[idx++] = x;
        }else if(s == "pop"){
            if(idx > 0) idx--;
        }else if(s == "query"){
            if(idx > 0)
                cout << st[idx - 1] << "\n";
        }else if(s == "empty"){
            if(idx > 0){
                puts("NO");
            }else{
                puts("YES");
            }
        }
    }
    return 0;
}

练习题：3302. 表达式求值 - AcWing题库

队列

实现一个队列，队列初始为空，支持四种操作
1. push x  -  向队列插入一个数 x;
2. pop -从队头弹出一个数
3. empty - 判断队列是否为空;
4. query - 查询队头元素
现在要对队列进行M个操作，其中的每个操作3和操作4都要输出相应的结果。
输入格式
第一行包含整数M，表示操作次数
接下来 M 行，每行包含一个操作命令，操作命令为push xquery 中的一种popiempty，
输出格式
对于每个empty和query操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或NO，query 操作的查询结果为一个整数，表示队头元素的值
数据范围
1≤M≤100000,
1≤x≤10^9,
所有操作保证合法。
输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], h = 0, idx = 0;
int main()
{
	int m;
	cin >> m;
	while(m --){
		string s;
		cin >> s;
		if(s == "push"){
			int x; cin >> x;
			e[idx++] = x;//插入
		}else if(s == "pop"){
			if(idx > h){
				h ++;//出队，头指针往后移
			}
		}else if(s == "empty"){
			if(h == idx){//判断是否为空
				puts("YES");
			}else{
				puts("NO");
			}
		}else if(s == "query"){//队头
			if(idx > h){
				cout << e[h] << "\n";
			}
		}
	}
	return 0; 
}

单调栈

单调栈维护栈中的元素必须满足单调性【单调上升，单调下降】

给定一个长度为 V的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。
输入格式
第一行包含整数 N，表示数列长度第二行包含N个整数，表示整数数列
输出格式
共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出 -1
数据范围

1≤N≤10^5
1≤数列中元素≤10^9
输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

暴力：遍历每个数，然后从当前元素往前找，找到第一个比它小的数。

思路：通过栈先进后出的特性，遇到比栈顶元素大的就出栈，知道比它小的就是离当前元素最近且比当前元素小的元素。 

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	stack<long long > st;
	while(n --){
		long long x;
		cin >> x;
		while(!st.empty() && st.top() >= x)st.pop();
		if(!st.empty()){
		    cout << st.top() <<" ";
		}else{
		    cout << "-1 ";
		}
		st.push(x);
	}
	return 0;
 } 

单调队列

【滑动窗口】

给定一个大小为n ≤10 ^ 6的数组
有一个大小为k 的滑动窗口，它从数组的最左边移动到最右边.
你只能在窗口中看到k个数字
每次滑动窗口向右移动一个位置
以下是一个例子:
该数组为[1 3 -1 -3 5 3 6 7]，k为3
窗口位置

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行
第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度第二行有n个整数，代表数组的具体数值
同行数据之间用空格隔开
输出格式
输出包含两个
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值
输入样例:

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

输出样例：

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

思路：存这个固定窗口 的下标，并且维护窗口的单调性。在窗口滑动过程中，要判断窗口前的元素是否需要出来，以及窗口的个数和单调性。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int main()
{
	int n, k; cin >> n >> k;
	for(int i = 0; i < n; i++)cin >> a[i];
	int h = 0, t = -1;
	for(int i = 0; i < n; i++){
		if(h <= t && q[h] < i - k + 1)h++;
		while(h <= t && a[q[t]] >= a[i])t--;
		q[++t] = i;
		if(i >= k-1)cout << a[q[h]] << " ";
		
	}
	cout << "\n";
	h = 0, t = -1;
	for(int i = 0; i < n; i++){
		if(h <= t && q[h] < i - k + 1)h++;
		while(h <= t && a[q[t]] <= a[i])t--;
		q[++t] = i;
		if(i >= k-1)cout << a[q[h]] << " ";
		
	}
	cout << "\n";
	return 0;
}

使用deque容器队列实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N];
int main()
{
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++)cin >> a[i];
	deque<int> dq;
	for(int i = 0; i < n; i++){
		if(dq.front() < i - k + 1)dq.pop_front();//队头下标未在窗口内
		while(!dq.empty() && a[dq.back()] >= a[i])dq.pop_back();//维持递增序列
		dq.push_back(i);
		if(i + 1 >= k)cout << a[dq.front()] << " ";//达到长度为k的窗口
	}
	cout << "\n";
	dq.clear();
	for(int i = 0; i < n; i++){
		if(dq.front() < i - k + 1)dq.pop_front();
		while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
		dq.push_back(i);
		if(i + 1 >= k)cout << a[dq.front()] << " ";
	}
	return 0;
 } 

KMP字符串

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串P在字符串S中多次作为子串出现
求出模式串P在字符串S中所有出现的位置的起始下标
输入格式
第一行输入整数N，表示字符串 P的长度
第二行输入字符串P
第三行输入整数M，表示字符串S的长度
第四行输入字符串S
输出格式
共一行，输出所有出现位置的起始下标(下标从0开始计数)，整数之间用空格隔开
数据范围
1≤N≤10^5
1≤M≤10^6
输入样例：

3
aba
5
ababa

输出样例：

0 2

对于p = "abcab"，next数组

next[1] = 0 , 前缀 ={}， 后缀 = {}；
next[2] = 0 , 前缀 ={a}， 后缀 = {b}
next[3] = 0 , 前缀 ={a, ab}， 后缀 = {c, bc}
next[4] = 1 , 前缀 ={a, ab,  abc}， 后缀 = {a, ca, bca}
next[5] = 2 , 前缀 ={a, ab, abc, abca}， 后缀 = {b, ab, cab, bcab}

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
// KMP算法 
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
	cin >> n >> p + 1 >> m >> s + 1;//两个字符串均从下标 1 开始 
	for(int i = 2, j = 0; i <= n; i++){
		while(j && p[i] != p[j+1])j = ne[j];//匹配不上 
		if(p[i] == p[j+1])j++;
		ne[i] = j;
	}
	for(int i = 1, j = 0; i <= m; i++){
		while(j && s[i] != p[j+1])j = ne[j];
		if(s[i] == p[j+1])j ++;
		if(j == n){
			cout << i-n << " ";
			j = ne[j];//继续匹配下一个子串 
		}
	}
	return 0;
}

本篇讲述最基本的数据结构：单链表，双链表，栈和队列，以及单调栈，单调队列，KMP字符串。对于最基本的数据结构，在C++中可以用stl中的容器 vector， deque，stack和queue。

今天又是努力了的一天！

"困难像弹簧，你弱它就强，你强它更强。" —亨利·福特